VOTERS - Editorial

editorial
, , ,
1

Problem Link - Discrepancies in the Voters List Practice Problem in 1000 to 1400 difficulty problems

Problem Statement:

The problem is to find ID numbers that appear in at least two of the three given sorted lists.

Approach:

Using a Frequency Map:

  • Use a data structure like a dictionary or a hash map to store the count of each ID number across the three input lists.
  • Traverse through each list and increment the count for each ID number in the map to keep track of how many times each ID appears.

Filtering Voters:

  • Iterate through the frequency map and collect ID numbers that appear in at least two of the three lists (i.e., with a count of 2 or more).
  • Store these qualifying ID numbers in a container such as an array or list.

Sorting:

  • Since the input lists are sorted and the goal is to output the unique ID numbers that appear in at least two lists, ensure that the final list of ID numbers is sorted before outputting them.

Complexity:

  • Time Complexity: Counting the IDs - O(N1+N2+N3). Collecting and sorting the output - O(M log ⁡M) where M is the number of unique ID numbers in the final list.
  • Space Complexity: O(N1+N2+N3) for storing IDs and their counts