Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. Find the first repeated number.

Overview

Naive Approach

The most basic way to solve this algorithm, is to have a nested for loop, where we can loop through each element in the array and then scan the array to check if a duplicate exists. While that can solve the problem, it is not efficient and if the array is large enough, it can take a long time to solve. The time complexity for this would be quadratic O(n^2).

Improved Solution - Use a HashSet

A hashset is used to store the values we iterate on, so we can later check if the value exists in the hashset to determine if the value is a duplicate. This will allow to only loop through the array once and keeping the time complexity low.

Use a HashSet Time Complexity

The algorithm is solved in linear time of O(n) as in worst case scenario, we need to iterate through the whole array.

Use a HashSet Space Complexity

Space complexity is O(n) as well, as we may need to store all elements in the set.

Use a HashSet Java Source Code

        public int findFirstDuplicateSet(int[] array) {
            final Set<Integer> numberSet = new HashSet<>();

            for (var number : array) {
                if (numberSet.contains(number)) {
                    return number;
                } else {
                    numberSet.add(number);
                }
            }
            return -1;
        }

Optimal Solution - In place array update & map array indexes to values.

Note: This following can work only because we know that the values of the array are ranging from 1-N. It may be a bit confusing at first. I had to review the algorithm a few times to understand.

What we can do here is map indexes to actual values. For example when we encounter a 2:

• Start off by retrieving the absolute value of the iterated element on the current index. Because we may have made this negative.
• Subtract 1 from the value on current index => 2-1 = 1
• Peek into index 1
• If the value at index 1 is positive, then make it a negative. This is because later on, when we find another 2, we will check the same index and since it is negative, we will know we found the duplicate value.
• If the value at index 1 is negative, return the absolute value of array at the index we are at and we are done.

In place array update & map array indexes to values overview

In place array update Java Source code

    public int findFirstDuplicateOptimal(int[] array) {

        for (int number : array) {
            final var indexToLook = Math.abs(number) - 1;

            if (array[indexToLook] < 0) {
                return Math.abs(number);
            } else {
                array[indexToLook] = array[indexToLook] * (-1);
            }
        }
        return -1;
    }

In place array update Time Complexity

The algorithm is solved in linear time O(n) as in worst case scenario, we would still need to iterate through the whole array.

In place array update Space Complexity

Space complexity is O(1). No Need for extra space. Super nice!

Conclusion

Hong Kong cinema is something you can’t duplicate anyway.

Martin Scorsese