First missing integer in an unsorted array

Problem statement – Given an unsorted integer array, find the first missing positive integer. Example,

  • If A = [-1, 4, 2, 3, 5], missing integer = 1.
  • If A = [1, 5, 2, 3, 4, 7], missing integer = 6.
  • If A = [-1, -2, -3, -4], missing integer = 1.

Clues

  • Your solution should be O(N) in time and O(1) in space.
  • Can you make changes in the array such that you can mark which numbers in 1 to N are already present in the array?

Solution – This is a little difficult one, so pay attention! If you go through the problem statement carefully, your solution will be an integer between 1 to N + 1, where N is the size of the array. Why N + 1? If the array had all integers from 1 to N, then the missing integer would be N + 1!

Now that we know our solution will be an integer from 1 to N + 1, we need to come up with a mechanism to mark/flag the numbers in 1 to N + 1, which are already present in the array. If we could use O(N) space, then we could create a boolean array isPresent[] of size N + 1, and set isPresent[A[i]] = true. The solution would be something like this –

boolean[] isPresent = new boolean[N + 1];

for (int i = 0; i < A.length; ++i) {
    isPresent[A[i]] = true;
}

for (int i = 1; i < isPresent.length; ++i) {
    if (!isPresent[i]) {
        return i;
    }
}

return N + 1;

But since our solution should be O(1) in space, we need to do this marking in our input array itself. Can we take advantage of the fact that the indices of an array is a contiguous span of numbers from 1 to N? Yes!

We will do this by making numbers at certain indexes negative. The idea is that, let’s say, we have A[i] = 3, then we will make A[3] negative. So that, when we make another scan of the array A, and we see A[3] is negative, we know that 3 has occurred somewhere in the array. Read the previous sentence once more, let it sink in. Now let’s write it as a formula –

int value = A[i];
A[value] = -A[value];

Now the question is, what if A[i] is negative? Let’s handle that case in our newly born formula.

int value = Math.abs(A[i]);
A[value] = -A[value];

Now the question is, what if A[value] is already negative? Let’s handle that case in our formula –

int value = Math.abs(A[i]);
A[value] = -Math.abs(A[value]);

So we will apply this formula to all the elements in the array by iterating over the whole array. Now, we will make another iteration over the array. If at any index i, we get A[i] as positive, then it means that the integer i was not present in the input array, otherwise A[i] would have been negative! So integer i is our missing integer. Read the solution again if you didn’t understand it in the first reading (I didn’t either 😛 )

Before you race off to code, there are a couple of issues we must handle. Firstly, what if we have negative integers or integers greater than N in our array? We know that our solution will be an integer between 1 and N + 1, so any other integer is junk for us. So we can replace all of them with a constant, say a variable called FLAG. So, when we encounter them in our formula loop, we can ignore them. Now keep in mind that they might have become negative because of some other element in the array. So, in our formula loop, we must ignore elements with values FLAG and -FLAG.

Secondly, up until now, for the sake of simplicity we spoke in terms of 1 indexed arrays, but we know that in real code, we have 0 indexed arrays. I guess you can handle that 😉

Code

public class Solution {
	public int firstMissingPositive(ArrayList<Integer> a) {
	    final int N = a.size();     // size
	    // a dummy value to replace
	    // integers below 0 and above N
	    final int FLAG = N + 2; 
	    
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) <= 0 || a.get(i) > N) {
	            a.set(i, FLAG);
	        }
	    }
	    
	    // Our formula loop
	    for (int i = 0; i < N; ++i) {
	        if (a.get(i) == FLAG || a.get(i) == -FLAG) {
	            continue;
	        }
	        
	        int value = Math.abs(a.get(i));
	            
	        a.set(value - 1, -Math.abs(a.get(value - 1)));
	    }
	    
	    // Loop through collection. Whichever
	    // index holds a +ve integer is the answer
	    for (int i = 0; i < N; ++i) { if (a.get(i) > 0) {
	            return i + 1;
	        }
	    }
	    
	    // If the collection has all integers
	    // from 1 to N, then answer is N + 1
	    return N + 1;
	}
}

Maximum sum contiguous sub-array

Problem statement – Given an array, find a contiguous sub-array whose sum is maximum. More precisely, if we have an array A[0, 1, 2 … N], we need to find a sub-array A[i, i + 1, i + 2, … j] such that the sum of elements in the sub-array is maximum.

Clues

  • Your solution should be O(N) in time and O(1) in space.
  • Can you think of a solution which solves the problem in a single scan of the array?

Solution – This is a popular interview question asked by the interviewers to test the basics of the candidate. This problem can be solved in O(N) time by using Kadane’s Algorithm. In this algorithm, we keep adding elements to a sum variable as we are traversing the array. This sum variable holds the sum of a sub-array. When the sum variable becomes negative, we cast off the the sub-array seen so far and reset sum variable. The final answer will be the maximum of all the values which were stored in sum over all iterations.

Example – For the array A = [-2 , 1, -3, 4, -1, 2, 1, -5, 4]

A[i] Sub-array sum Max sub-array maxSum
-2 [-2] 0 [-2] -2
1 [1] 1 [1] 1
-3 [-3] 0 [1] 1
4 [4] 4 [4] 4
-1 [4, -1] 3 [4] 4
2 [4, -1, 2] 5 [4, -1, 2] 5
1 [4, -1, 2, 1] 6 [4, -1, 2, 1] 6
-5 [-5] 3 [4, -1, 2, 1] 6
4 [-5, 4] 3 [4, -1, 2, 1] 6

Code

public class Solution {
	public int maxSubArray(List<Integer> a) {
	    int sum = 0;
	    int maxSum = Integer.MIN_VALUE;
	    
	    for (int i = 0; i < a.size(); ++i) {
	        if (sum + a.get(i) < 0) {
	            // Adding this element will make the current
	            // subarray sum negative, so don't add this element
	            // and start a new subarray with next element
	            sum = 0;
	        } else {
	            // Adding this element will increase the
	            // current subarray sum, so add this
	            // element to the current subarray
	            sum += a.get(i);
	        }
	        
	        // maxSum is the maximum of -
	        //
	        // 1. maxSum so far
	        // 2. if sum == 0, then a.get(i) which is proably a -ve number
	        // 3. if sum != 0, then sum of subarray so far
	        maxSum = Math.max(maxSum, sum == 0 ? a.get(i) : sum);
	    }
	    
	    return maxSum;
	}
}

If you didn’t understand why we need the “sum == 0 ? a.get(i) : sum” condition in the end, think of the case where array A = [-3, -2, -1]. Basically when the array has all negative values, you’d want to return the largest among the negative values. Now remember, sum variable doesn’t store negative values, so when it holds 0, we consider A[i] instead of sum. Give it a little thought, I’m sure you’ll understand it. If you need a more explanation, refer to my post on Kadane’s Algorithm.

Find the majority element in an array

Problem statement – Given an unsorted array, find the majority element (element which occurs for more than N/2 times).
Clues

  • Solution must be O(N) in time and O(1) in space.
  • If the majority element exists, there will only be one such element. How can we find it?

Solution – We can do this in O(N) time by the Boyer–Moore majority voting algorithm. It is a simple 3-step algorithm –

  • Initialization – We will take 2 variables, ‘candidate’ and ‘votes’ and set them to 0.
  • Voting – Traverse through the array once. If votes is 0, then we set candidate to the current element. We will also check, if the current element (arr[i]) is equal to the candidate, if yes, increment votes, else decrement.
  • Checking the winning candidate – After Step 2, we will compute the frequency of the value in candidate. If this is more than N/2, then the candidate is the majority element, otherwise, the majority element does not exist.

So this is kind of like picking a candidate and computing how many votes he has. You may not understand it in the first glance, but try reading the logic two more times and try to write the pseudo-code for this. Believe me, this is a ridiculously simple algorithm!

Code

// Moore's Majority Voting Algorithm procedure
// Computes the majority element in O(N) time
// Returns the majority element
// If no majority element, returns INT_MIN
int majorityElement(int arr[], int length)
{
    int votes = 0, candidate = -1, i;
     
        // Voting
    for (i = 0; i < length; ++i) {
        if (votes == 0) {
            candidate = arr[i];
        }
         
        if (candidate == arr[i]) {
            ++votes;
        } else {
            --votes;
        }
    }
     
    votes = 0;
     
    // Get freq. of candidate
    for (i = 0; i < length; ++i) { if (arr[i] == candidate) { ++votes; } } // Verify if the candidate // is the majority element if (votes > length / 2) {
        return candidate;
    } else {
        return INT_MIN;
    }
}

Find pivot element in a sorted and rotated array

Problem Statement – Suppose we have a sorted array, and now we rotate it N times, find the pivot element. The pivot element would be the largest element. Also, can you calculate N?

Clues

  • Solution should be O(log N) in time and O(1) in space.
  • Can you think of  a binary search based solution where you keep comparing the middle element with the last element?

Solution – The pivot element is basically, the largest element in an array. For a sorted and rotated array, it might be somewhere in between. We can solve this in O(log N) time, through a divide-and-conquer approach, which is similar to peak finding algorithm. We will have the lower limit (low) and the upper limit (high) from which we will calculate the ‘mid’. Now, we must address a few cases –

  • arr[mid] > arr[high] – If the mid element is greater than the last element, then the pivot should be in the second half of the array. Why is this so? This is actually because it is a sorted and rotated array. You may not understand this at first, but think of the values of the elements in the array as a histogram. Try to understand the picture below, I’m sure you can figure out why this happens –
    Pivot Element - Case 1

    Pivot Element – Case 1

  • arr[mid] < arr[high] – If the mid element is less than the last element, then the pivot should be in the first half of the range.
    Pivot Element - Case 2

    Pivot Element – Case 2

  • If mid element is a peak – If the mid element satisfies the property of the peak element (not lesser than its neighbors), then, it is the pivot.
If we can put these conditions, and handle the trivial cases, we can compute the pivot element. The number of times the array is rotated would be (IndexOfPivotReturned + 1).

Code

C
// A Divide-and-Conquer approach to find the pivot (highest) element in
// a sorted rotated array - returns the index of the pivot -> O(log N)
int peakElement(int arr[], int low, int high, int lowerBound, int upperBound)
{
	int mid = low + (high - low) / 2;
	
	if (mid == lowerBound) {
		if (mid == upperBound) {
			// Only 1 element
			return mid;
		} else if (arr[mid] >= arr[mid + 1]) {
			// Pivot is the greater element
			return mid;
		}
	} else if (mid == upperBound) {
		if (arr[mid] >= arr[mid - 1]) {
			// Pivot is the greater element
			return mid;
		}
	} else {
		if (arr[mid] >= arr[mid + 1] && arr[mid] >= arr[mid - 1]) {
			// Mid value is the pivot
			return mid;
		} else if (arr[mid] > arr[high]) {
			// The Pivot is in the second half
			return peakElement(arr, mid + 1, high, lowerBound, upperBound);
		} else if (arr[mid] < arr[high]) {
			// The Pivot is in the first half
			return peakElement(arr, low, mid - 1, lowerBound, upperBound);
		}
	}
	
	return -1;
}

Kth smallest element in an array

Problem Statement – Given an unsorted array of N elements, find the kth smallest element. kth smallest element is the element at index k if the array were sorted.

Clues

  • Solution should be O(N) in time and O(1) in space.
  • Can you think of a divide-and-conquer based solution?
  • Can you apply Quicksort’s partitioning logic here?

Solution – This can be done in O(N) time and O(1) space by the Quickselect Algorithm. The Quickselect Algorithm is a very useful divide-and-conquer based algorithm which rearranges the array such that the kth element is the kth smallest element in the array. A step-by-step version of Quickselect is –

  •  Calculate the middle element for the given range.
  • Place all the elements greater than the mid element to its right.
  • Place all the elements lesser than the mid element to its left.
  • If ‘k’ is less than the index of the middle element, then recursively call Quickselect on the left half of the range.
  • If ‘k’ is greater than the index of the middle element, then recursively call Quickselect on the right half of the range.

Code

C
// Quick Select procedure to search for
// the kth smallest element in O(N) time.
void quickSelect(int arr[], int low, int high, int k)
{
    if (high - low < k) {
        // A single element is 
        // considered to be sorted
        return;
    }
     
    int mid = low + ((high - low) / 2);
     
    // Put the pivot at the last
    int temp = arr[mid];
    arr[mid] = arr[high];
    arr[high] = temp;
     
    int pivot = arr[high];
    int i = low;
    int j = high - 1;
     
    // The partition
    while (j >= i) {
        if (arr[j] < pivot && arr[i] > pivot) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
             
            ++i;
            --j;
        } else if (arr[j] < pivot && arr[i] <= pivot) {
            ++i;
        } else if (arr[j] >= pivot && arr[i] > pivot) {
            --j;
        } else if (arr[j] >= pivot && arr[i] <= pivot) {
            ++i;
            --j;
        }
    }
     
    // Bring the pivot back to its
    // appropriate place
    temp = arr[i];
    arr[i] = arr[high];
    arr[high] = temp;
     
    if (k >= i) {
        quickSelect(arr, i + 1, high, k);
    } else {
        quickSelect(arr, low, i, k);
    }
}