algoadvance

Leetcode 961. N

Problem Statement

Given an array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times. Return the element that is repeated N times.

Clarifying Questions

  1. Input Constraints:
    • Can we assume the array A always has exactly one element repeated N times?
    • What are the constraints on the elements of the array? (e.g., range of values)
  2. Output:
    • Should we handle any specific edge cases? (e.g., invalid inputs)

Strategy

To solve this problem efficiently, I will use the following approach:

  1. Hash Set to Track Seen Elements:
    • Traverse through the array while maintaining a set of seen elements.
    • For each element, check if it’s already in the set.
    • If it is, then this is the repeated element, so return it.
    • If it is not, add the element to the set.

This approach ensures that we only make a single pass through the array and keep an auxiliary space proportional to the number of unique elements, which makes the algorithm efficient in terms of both time and space.

Time Complexity

Code

#include <vector>
#include <unordered_set>

class Solution {
public:
    int repeatedNTimes(std::vector<int>& A) {
        std::unordered_set<int> seen;
        for(int num : A) {
            if(seen.count(num)) {
                return num;
            }
            seen.insert(num);
        }
        // If input constraints are guaranteed, the function will always return from within the loop.
        return -1;
    }
};

Explanation

  1. Initialization:
    • Initialize an empty unordered set seen to keep track of elements we have encountered.
  2. Iteration:
    • Loop through each element num in array A.
    • For each num, check if it exists in the set seen.
      • If it does, this is the repeated element, so return num.
      • If it does not, insert num into the set.
  3. Safety Net:
    • If the input constraints guarantee that there’s always one repeated element, the function will not reach the return statement outside the loop.
    • Otherwise, this return statement is just a safety net in case of unexpected inputs.

By iterating through the array and checking for the repeated element as described, the solution ensures we find the N-repeated element efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI