Negative marking

2 minute read

The Problem

Find the repeating and the missing: Given an unsorted array of size n. Array elements are in the range from 1 to n. One number fron input array is missing and one number occurs twice in the array. Find these two numbers without using extra space. Examples:

Input: [3, 1, 3]
Output: missing = 2, repeating = 3
Explanation: In the array, 
2 is missing and 3 occurs twice 

Input: [4, 3, 6, 2, 1, 1]
Output: missing = 5, repeating = 1

The Solution

The problem is very similar to the problem I mentioned in the sum technique. However, the sum technique will not work because we need to find 2 unknow variables in this problem, and you cannot solve 2 variables with only 1 linear equation. It is well known in linear algebra that you need n distinct equations to solve n variables.

We observe that:

  1. The numbers in the array is from 1 to n, so there is no zero and negative numbers.
  2. There is exactly 1 missing and 1 repeated number

Typically to detect duplicate, we can use a set or hash table to keep track of numbers that have been seen when we iterate through the array, but this will require extra auxiliary O(n) space.

To keep track of numbers that we have seen without using extra space, we need to modify the input array. There are many ways we can modify, for this particular problem, since input numbers are positive, so we can keep track of a number by negating it.

def find_missing_repeat(nums):
    repeat, missing = None, None
    for i, n in enumerate(nums):
        idx = abs(n)-1
        if nums[idx] > 0:
            nums[idx] *= -1
       	else:
       		repeat = abs(n)

    # No we look for missing number
    for i, n in enumerate(nums):
    	if n > 0:
    		missing = i + 1
    		return missing, repeat
func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func findMissingRepeat(nums []int) (int, int, bool) {
	var missing, repeat int
	for _, n := range nums {
		idx := abs(n) - 1
		if nums[idx] > 0 {
			nums[idx] *= -1
		} else {
			repeat = abs(n)
		}
	}

	for i, n := range nums {
		if n > 0 {
			missing = i + 1
			return missing, repeat, true
		}
	}

	return missing, repeat, false
}
	

The Analysis

The complexity of the solution above is straightforward, we iterate the array twice and so it is linear time or O(n).

Modifying input is useful if the problem is constrained by constant space. It is worth mentioning that negative marking is just 1 way to track the number, out of many. In the next section, we will see another useful technique.

Similar problems:

Leetcode 448. Find All Numbers Disappeared in an Array Find duplicates in O(n) time and O(1) extra space

Updated:

Leave a comment