Simple clear explanation of Solution with Simple code to Understand


  • 2
    R

    The solution for this problem is pretty Simple. All the solutions I have seen so far do not provide much explanation. My explanation is for people like me, who are trying to understand the solution rather than writing extremely short code to reduce the number of lines. So here is the solution.

    In the given problem, we need to find the first positive number that is missing. We consider this number to be greater than zero. The input array also contains negative numbers. The main idea behind this solution is that, we try to put the numbers in their right indices. if we want to keep an element A[i] in its right place, we keep it at index A[i]-1 because Arrays are Zero indexed.

    Now when we scan the array, there are two conditions. the number is positive or negative.

    1. If the number is negative we just ignore it.
    2. If the number is positive, we have four cases.
      a. if the number A[i] is greater than the length of the array, we cannot keep it in its right index ie., A[i]-1. So we just increment the counter.
      b. if the number A[i] is already at the right index, that is A[i] == i+1, we just increment the counter.
      c. if the number is a duplicate and the correct number is already in the right place, ie., A[i] == A[A[i]-1], we just increment the counter.
      d. finally, if none of the above cases satisfy, it means that this number must be placed in the correct place. So we swap it with the number at A[i]-1;

    Now the number at A[i]-1 can belong to two types.

    a. Zero or A negative number
    b. This number is greater than the length of the given array.

    when we keep doing this swap, at the location of missing number, either of the above mentioned numbers would be present, making us easy to identify the missing number. Here is the code for the same.

    
    public class Solution {
        public int firstMissingPositive(int[] A) {
            
            int i= 0;
    
            while(i < A.length){
                if(A[i] <= 0){
                    i++;
                }else{
                    if(A[i] > A.length){
                        i++;
                    }else if(A[i] == i+1){
                        i++;
                    }else if(A[i] == A[A[i]-1]){
                        i++;
                    }else{
                        swap(A, i, A[i]-1);
                    }
                }
            }
    
            i=0;
            while(i < A.length && A[i] == i+1){
                i++;
            }
    
            return i+1;
        }
        
        private void swap(int[] A, int i, int j){
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    }
    
    

    Thanks,


Log in to reply
 

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