forced push

Problem 4

February 04, 2023

Ah, algorithms. The kale of the tech world. We all pretend to love them because they're "good for us," but deep down, we'd rather work on anything else. But here we are, sipping on our green smoothie of algorithms, because, let's face it, they're part of the tech fitness routine.

Remember that iconic moment when Michael Jordan, with the flu, still managed to score 38 points against the Utah Jazz in the '97 NBA Finals? Yeah, that's how I feel every time I tackle an algorithm. Slightly nauseated, definitely under the weather, but hey, the game must go on. And just like MJ, we might not enjoy every moment, but we recognize the greatness that comes from pushing through.

In today's episode of "Why Is This Algorithm Even a Thing?", we're diving into our fourth coding challenge.

❓ PROMPT

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

You can modify the input array in-place.

🔍 EXPLORE

Sounds simple, right? But we need to do this in-place!? Let's break this down.

Assumptions

  1. The array can contain any integer, including negatives and zeros.
  2. The array can have duplicates.
  3. We're looking for the smallest positive integer that's missing from the array.
  4. We can modify the input array in-place.

Discoveries

  1. If the array has no positive integers, the answer is 1.
  2. If the array length is n, then the answer will always be in the range [1, n+1]. This is because, in the worst case, the array will have all numbers from 1 to n, and the answer will be n+1.

Edge/Corner Cases

  1. Empty array.
  2. Array with all negative numbers.
  3. Array with all positive numbers in a sequence.
  4. Array with duplicates.

🗣️ CLARIFYING QUESTIONS

The challenge seems clear, but let's clarify one thing:

  1. What should be the output for an empty array? (Assuming it's 1 since there's no positive integer in the array.)

💡 BRAINSTORM

Approach 1: Sorting

  1. Sort the array.
  2. Traverse the sorted array and find the first missing positive integer.
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)

Approach 2: Hashing

  1. Use a hash set to store all numbers in the array.
  2. Traverse from 1 to n+1 and check the first number that's not in the hash set.
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Approach 3: In-place modification (Fits the requirements)

  1. Traverse the array and for every positive number x, try to place it at the index x-1.
  2. Traverse the array again and find the first index where the number is not index+1.
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Master Plan: We'll go with Approach 3 since it meets the challenge's requirements of linear time and constant space.

📝 PLAN

  1. Traverse the array. For each positive number x:
  • While x is positive, within the array's bounds, and array[x-1] is not x:
    • Swap array[x-1] and x.
  1. Traverse the array again:
  • If array[i] is not i+1, return i+1.
  1. If all numbers are in place, return n+1.

🛠️ IMPLEMENT

func firstMissingPositive(_ nums: [Int]) -> Int {
    var nums = nums
    rearrangeToConsecutivePositions(&nums)
    return findFirstMissingPositive(nums)
}

private func rearrangeToConsecutivePositions(_ nums: inout [Int]) {
    let n = nums.count
    for i in 0..<n {
        while nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i] {
            nums.swapAt(i, nums[i] - 1)
        }
    }
}

private func findFirstMissingPositive(_ nums: [Int]) -> Int {
    for i in 0..<nums.count {
        if nums[i] != i + 1 {
            return i + 1
        }
    }
    return nums.count + 1
}

🧪 VERIFY

let test1 = [3, 4, -1, 1]
let test2 = [1, 2, 0]
let test3 = [-5, -3, -1]
let test4 = [1, 1, 1, 1]
let test5 = [Int]()
let test6 = [2, 2, 2, 6, 1, 5, 4]

assert(firstMissingPositive(test1) == 2, "A standard case with mixed positive and negative numbers.")
assert(firstMissingPositive(test2) == 3, "Another standard case with zero included.")
assert(firstMissingPositive(test3) == 1, "All negative numbers.")
assert(firstMissingPositive(test4) == 2, "All duplicates of the same number.")
assert(firstMissingPositive(test5) == 1, "An empty array.")
assert(firstMissingPositive(test6) == 3, "A mix of duplicates and unique numbers.")

📊 ANALYZE

This approach has a time complexity of O(n) and a space complexity of O(1). This is because we traverse the array a constant number of times (at most 3 times), and we use a constant amount of space regardless of the input size. The solution is efficient given the constraints, and there might be minor improvements in terms of code readability, but the overall approach seems optimal for this problem.

📚 FINAL THOUGHTS

Ah, this question? It's like hearing the opening chords of "Stairway to Heaven" at a guitar store. Predictable? Absolutely. Overplayed? Most definitely. But does it test your mettle and make sure you've got the basics down? Oh, you bet. It's the coding equivalent of that song everyone thinks they can play until they're put on the spot. And just like every amateur guitarist who thinks, "How hard can it be?", we dive into these algorithmic classics, hoping we won't botch the solo.

This question might seem like a rehashed version of every other array problem out there, it does have its merits. It's not just about finding a missing number; it's about doing so efficiently. It's like being handed a puzzle and then being told half the pieces are missing, but you still need to figure out the whole picture.

What's revealing? Sometimes the most apparent solution isn't always the optimal one. Sorting? Too slow. Hashing? Too much space. The answer lies in array manipulation, swapping numbers until they find their place.

And let's not forget the edge cases. Why would an array just contain positive integers when it can also have zeros, negatives, and duplicates? It's like a party where everyone's invited, even those who weren't on the guest list.

Logo