Java O(n) Easy To Understand, Optimal Solution

  • 0

    The idea to this question is to take advantage of the fact that all values in nums fall into range [1, n], and are therefore initially positive.

    Suppose we're considering element nums[i] and we take its absolute value, x.

    1. If nums[x-1] > 0, then we haven't encountered value x yet in nums, so we mark that we've seen x by setting num[x-1] negative.
    2. If nums[x-1] < 0, then we have encountered value x once already in nums, so we append x to our result list.

    By the end, we should return a complete list of duplicate values within nums in result.

    Time Complexity
    The time complexity is O(n) where n is the number of elements in nums, since we iterate through all elements in nums once.

    class Solution {
        public List<Integer> findDuplicates(int[] nums) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                int absNum = Math.abs(nums[i]);
                // If the element at index absNum - 1 is negative, then
                //    we've visited element absNum before, append to result
                if (nums[absNum - 1] < 0) {
                // Mark that we've found 1 instance of absNum so far...
                else {
                    nums[absNum - 1] = -nums[absNum - 1];
            return result;

Log in to reply

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