forced push

Problem 1

February 01, 2023

I just signed up for Daily Coding Problem. A newsletter that emails out a coding problem each day. Hoping to at least attempt one problem each day. Here's what was sent out the first day. Let's get started practicing Polya's method.

❓ PROMPT

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

🔍 EXPLORE

Assumptions

  1. The list can contain both positive and negative numbers.
  2. The list might have duplicate numbers.
  3. The same number cannot be used twice for the sum unless it appears twice in the list.

Discoveries

  • If the list is empty or has only one number, it's impossible to find two numbers that sum to k.

Edge/Corner Cases to Consider

  • List with no numbers.
  • List with only one number.
  • List with duplicate numbers.
  • Negative numbers in the list.
  • k being 0 and the list having two zeros.

🗣️ CLARIFYING QUESTIONS

The challenge seems pretty clear, but just to be sure: Are there any constraints on the size of the list or the range of numbers it can contain?

💡 BRAINSTORM

Approach 1: Brute Force

  • Loop through each number and then loop again to check if the sum of the two numbers equals k.
  • Time Complexity: O(n2)
  • Space Complexity: O(1)

Approach 2: Using a Set

  • Traverse the list and for each number, calculate the difference between k and that number. Check if this difference exists in a set. If it does, we've found our pair.
  • Time Complexity: O(n)
  • Space Complexity: O(n)

Approach 3: Sorting and Two Pointers

  • Sort the list and use two pointers, one at the beginning and one at the end. If the sum of the two numbers is less than k, move the left pointer to the right. If the sum is more than k, move the right pointer to the left.
  • Time Complexity: O(n log n) for sorting + O(n) for finding the pair = O(n log n)
  • Space Complexity: O(1)

Master Plan: I'll go with Approach 2 using a set because it gives us the solution in one pass and has a linear time complexity.

📝 PLAN

  1. Initialize an empty set.
  2. Traverse the list.
  3. For each number, calculate the difference between k and that number.
  4. If the difference is in the set, return true.
  5. Otherwise, add the number to the set and continue.
  6. If we've traversed the entire list and haven't returned true, return false.
Initialize an empty set called seenNumbers
For each number in the list:
    Calculate the difference as k - number
    If difference is in seenNumbers:
        Return true
    Add the number to seenNumbers
End of loop
Return false

🖍️ DIAGRAM

Problem 1

🛠️ IMPLEMENT

func hasPairWithSum(_ numbers: [Int], _ k: Int) -> Bool {
    var seenNumbers = Set<Int>()
    
    for num in numbers {
        if seenNumbers.contains(k - num) {
            return true
        }
        seenNumbers.insert(num)
    }
    
    return false
}

💡 BRAINSTORM (Functional Approach)

  • Use the contains method to check if the list contains a number that, when added to the current number, equals k.
  • Use the reduce method to accumulate the seen numbers in a set.

📝 PLAN (Functional Approach)

Function hasPairWithSum(numbers, k):
    Initialize an accumulator with two properties: found (set to false) and seenNumbers (set to an empty set)
    
    For each number in the list, do the following using the reduce function:
        If found is true OR seenNumbers contains (k - current number):
            Set found to true and continue with the current seenNumbers
        Else:
            Continue with found set to false and add the current number to seenNumbers
    
    At the end of the reduce function, return the 'found' property of the accumulator
End Function

🖍️ DIAGRAM

Problem 1 Functional

🛠️ IMPLEMENT (Functional Approach)

func hasPairWithSum(_ numbers: [Int], _ k: Int) -> Bool {
    // Use the reduce function to iterate over the numbers and accumulate a result.
    // The accumulator (acc) consists of two parts:
    // 1. found: A boolean indicating if we've found a pair that sums to k.
    // 2. seenNumbers: A set of numbers we've seen so far.
    numbers.reduce((found: false, seenNumbers: Set<Int>())) { (acc, num) in
        
        // If we've already found a pair or the set contains a number that, when added to the current number, equals k...
        if acc.found || acc.seenNumbers.contains(k - num) {
            // ...return the current state of the accumulator with found set to true.
            return (true, acc.seenNumbers)
        }
        
        // Otherwise, add the current number to the set and continue.
        return (false, acc.seenNumbers.union([num]))
    }.found  // At the end, return the 'found' part of the accumulator.
}

🧪 VERIFY (Both Approaches)

Let's test our function with some test cases:

  • hasPairWithSum([10, 15, 3, 7], 17) should return true because 10 + 7 = 17.
  • hasPairWithSum([10, 15, 3, 7], 15) should return false because no two numbers sum up to 15.
  • hasPairWithSum([5, 5], 10) should return true because 5 + 5 = 10.

🔄 REVIEW AND REFACTOR

The code looks clean and adheres to the master plan. It's also optimized for a single pass through the list.

📊 ANALYZE

The final solution has a Time Complexity of O(n) and a Space Complexity of O(n). The limitation is that we're using extra space for the set. However, this approach is efficient for finding the pair in one pass.

💭 Is this question reminiscent of any other problem?

This is a classic coding interview question. It's similar to the "Two Sum" problem on LeetCode. Here's the link: Two Sum on LeetCode.

Final Thoughts

Tackling coding challenges can be a daunting task, but with the right strategy and approach, it there's a small change that it becomes an enjoyable journey of problem-solving. The "Two Sum" problem is a classic example that tests the ability to think about different solutions and their trade-offs. Whether you're using a brute force method, optimizing with data structures like sets, or diving into functional programming paradigms, the key is to understand the problem deeply and choose the right tool for the job. Remember, every problem has a solution; it's just a matter of finding the right path.

Logo