algoadvance

Leetcode 961. N

Problem Statement

You are given an array A that contains 2N elements. In this array, there is exactly one element that is repeated N times. Your task is to find that repeated element.

Example:

Input: [1, 2, 3, 3]
Output: 3

Input: [2, 1, 2, 5, 3, 2]
Output: 2

Input: [5, 1, 5, 2, 5, 3, 5, 4]
Output: 5

Clarifying Questions

  1. Input Size: What is the range of N?
    • Typically, the size of the array should be even and comfortably fits within typical memory constraints for a coding problem.
  2. Element Types: Are there any constraints on the types of elements in the array (e.g., are they all integers)?
    • It’s implied that they are integers given the examples.
  3. Uniqueness: Is there more than one element that can meet the criteria?
    • No, there is exactly one element that repeats N times.

Strategy

Given that one element repeats N times in an array of size 2N, the repeated element will be the only element meeting this criterion.

We can use the following strategies to solve this problem:

  1. HashMap / HashSet:
    • Traverse through the array and use a HashSet to keep track of elements we have seen.
    • As soon as we encounter an element that’s already in the set, we know it is the repeated one and return it.
  2. Brute Force:
    • For each element, count its frequency in the array.
    • This is less efficient and not recommended here since it will have a larger time complexity.

We’ll go with the HashSet approach for optimal time complexity and simplicity.

Code

import java.util.HashSet;

public class Solution {
    public int repeatedNTimes(int[] A) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : A) {
            if (!set.add(num)) {  // If add returns false, then num is already in set.
                return num;
            }
        }
        // According to the problem statement, there will always be a solution,
        // So this line should never be reached.
        return -1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr1 = {1, 2, 3, 3};
        int[] arr2 = {2, 1, 2, 5, 3, 2};
        int[] arr3 = {5, 1, 5, 2, 5, 3, 5, 4};

        System.out.println(solution.repeatedNTimes(arr1));  // Output: 3
        System.out.println(solution.repeatedNTimes(arr2));  // Output: 2
        System.out.println(solution.repeatedNTimes(arr3));  // Output: 5
    }
}

Time Complexity

This approach ensures that we find the N-repeated element efficiently.

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