Java: Optimal, generalizable solution with explanations. (Alternative method.)

  • 0

    This solution uses O(n) time and O(1) space.
    (By uncommenting one line, the input array could be left in it's original state.)
    This algorithm could also be generalized to find all the elements that appear k times in the array.

    public class Solution {
        public List<Integer> findDuplicates(int[] nums) {
            for (int i = 0; i < nums.length; i++)
                // Optimization A: Decrease each number in the array by one: Why?
                // This adjusted figure makes it much easier for us to work with because the range becomes 0 <= a[i] < n,
                // which can easily be indexed in the array by using with the mod (%) operation.
                // Optimization B: Just inline the originalValue to avoid having the overhead of storing the value.
                // Here is the pre-optimized code:
                //int originalValue = nums[i] % nums.length;
                //nums[originalValue] += nums.length;
                nums[nums[i] % nums.length] += nums.length;
            List<Integer> result = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++)
                // (nums[i] / nums.length) indicates the number of times this value was referenced.
                if ((nums[i] / nums.length) == 2)
                    // We must remember to add 1 to the result to reflect the original value. 
                    // (i.e. The original value was decremented by Optimization A, above.
                    result.add((i % nums.length) + 1);
                //nums[i] = (nums[i] % nums.length) + 1;   // Uncomment this line to return the array to its original state.
            return result;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.