We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Sparse Arrays
  2. Discussions

Sparse Arrays

  • kousiksen09
     + 0 comments

    C# - O(n) - The code iterates through the 'queries' list, and for each query, it performs a lookup in the dictionary 'frequency'. The dictionary lookup operation is O(1) on average. Therefore, the overall time complexity is O(n), where n is the number of elements in the 'queries' list.

    public static List<int> matchingStrings(List<string> strings, List<string> queries)
    {
        List<int> countArr = new List<int>();
        //distinct check not required
        //List<string> distQuery = queries.Distinct().ToList();
        var frequency = strings.GroupBy(x=>x).ToDictionary(x => x.Key, x => x.Count());
        foreach(var q in queries)
        {
            if(frequency.ContainsKey(q))
            {
            Console.WriteLine("{0} element has count of {1} ",q, frequency[q]);
            countArr.Add(frequency[q]);
            }
            else
            {
                countArr.Add(0);
            }
        }
        return countArr;
    }

}