O(1) space, O(N) time, no partition, no sorting solution


  • 0
    L

    Assume the length of the input array is N.
    We are only interested in the value in the range of 1 to N, all other values (zero, negative, bigger than N) are not our concern. Because if there is one positive number missing, it lies in between 1 to N, or no positive number is missing, in that case we return N + 1.
    Algorithm is to exchange all interesting numbers (1 to N) to its correct position, where correct position means position val - 1 for value val (array index zero based).

    Therefore, condition to exchange for a number val:

    1. val > 0;
    2. val <= N;
    3. val is not in its correct position;
    4. the position we want to move val to does not have the correct number (otherwise, incase of duplicate numbers, the 2 numbers will exchange forever, think about the test case {1, 1}).

    Code:

    public class Solution {
    	public static int firstMissingPositive(int[] nums) {
    		int n = nums.length;
    		int curIdx = 0;
    		while (curIdx < n) {
    			int cur = nums[curIdx];
    			if (cur <= 0 || cur > n || cur == curIdx + 1
    					|| nums[cur - 1] == cur) {
    				// out of range numbers, or already in the correct position, or
    				// target position already has the correct number
    				curIdx += 1;
    				continue;
    			} else {
    				// exchange to the correct position
    				nums[curIdx] = nums[cur - 1];
    				nums[cur - 1] = cur;
    			}
    		}
    
    		int ret = 1;
    		for (int i = 0; i < n; i++) {
    			if (nums[i] != i + 1) {
    				ret = i + 1;
    				return ret;
    			}
    		}
    		// all number are in the correct position, return the next bigger
    		// integer
    		return n + 1;
    	}
    }
    

Log in to reply
 

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