Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this problem is to take advantage of two important facts:

    1. All elements in input nums are initially positive
    2. All elements are within range [1, n], where n is the length of nums.

    So, for any element, x, in nums, we know that by fact 2), nums[x-1] exists.

    To mark which elements exist in nums for later use, we apply fact 1): if we encounter an element of value x and nums[x-1] > 0, by setting nums[x-1] = -nums[x-1], this informs us that element x exists within nums, BUT we may encounter negative indices from now on, so we must use absolute values to encounter only positive indices.

    // Example:
    //int [] nums = { 5, 5, 5, 5, 5 }
    
    // Suppose we're considering index 0 first. Since the absolute value of
    //    nums[0] equals 5 and nums[5-1] > 0, we set nums[5-1] = -nums[5-1].
    //    Our array now is { 5, 5, 5, 5, -5 }; this means 5 has been found.
    
    // nums = { 5, 5, 5, 5, -5 }
    
    // Suppose we're now considering index 4. Since the absolute value of 
    //    nums[4] equals 5 and nums[5-1] < 0, 5 has been found already, so we 
    //    don't need to set nums[5-1] = -nums[5-1].
    

    Lastly, we iterate through all elements. If we encounter an element, nums[i], where nums[i] > 0, then that means element i+1 was never encountered in nums.

    If you're confused about the x-1, i+1 logic, remember that the indices in nums span from 0...n-1 while the numbers we are tracking span from 1...n.

    Time Complexity
    The time complexity is O(n) where n is the number of elements in nums, since we iterate through nums twice - the first time to mark elements, the second time to generate our result.

    class Solution {
        public List<Integer> findDisappearedNumbers(int[] nums) {
            for (int num : nums) {
                int absNum = Math.abs(num);
                // We mark nums by setting the element at index absNum-1 
                //       as negative; this later tells us absNum exists
                if (nums[absNum - 1] >= 0) {
                   nums[absNum - 1] = -nums[absNum - 1];
                } 
            } 
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                // If the number is positive, it means value (i+1) not found
                if (nums[i] > 0) {
                    result.add(i + 1);
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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