coderz.py

Problem Statement (Asked By Google)

Given a list of integers and a target number k, determine if there exist two numbers in the list whose sum equals k.

For example, given [10, 15, 3, 7] and k = 17, return True because 10 + 7 = 17.

Bonus: Can you solve this in a single pass?

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

Problem link: https://leetcode.com/problems/two-sum/

Solution:

This problem can be solved in a variety of ways.

Approach 1: The brute force approach involves iterating through every possible pair of numbers in the array:

public boolean twoSum(int[] nums, int k) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (i != j &amp;&amp; nums[i] + nums[j] == k) {
                return true;
            }
        }
    }
    return false;
}

This approach has a time complexity of O(N^2).

Approach 2: Another method is to use a set to store the numbers we’ve already seen. For each number, we check if there’s another number in the set that, when added, equals k.

import java.util.HashSet;

public boolean twoSum(int[] nums, int k) {
    HashSet<Integer> seen = new HashSet<>();
    for (int num : nums) {
        if (seen.contains(k - num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}

This approach has a time complexity of O(N), as set lookups take O(1).

Approach 3: Another solution involves sorting the array first. Once sorted, we iterate through the array and use binary search to look for k−nums[i].

import java.util.Arrays;

public boolean twoSum(int[] nums, int k) {
    Arrays.sort(nums); // Sort the array
    for (int i = 0; i < nums.length; i++) {
        int target = k - nums[i];
        int j = binarySearch(nums, target);

        // Ensure binary search finds a valid index and check edge cases
        if (j == -1) {
            continue;
        } else if (j != i) {
            return true;
        } else if (j + 1 < nums.length &amp;&amp; nums[j + 1] == target) {
            return true;
        } else if (j - 1 >= 0 &amp;&amp; nums[j - 1] == target) {
            return true;
        }
    }
    return false;
}

private int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return -1;
}

Since binary search runs in O(log⁡N) and we perform it N times, the total time complexity is O(Nlog⁡N). This approach uses O(1) extra space.

This approach sorts the array first and then uses binary search to find the required complement efficiently.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.