Two Sum II

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Intuition

Top Of The Morning Lads,

Another classic here! The famous (frankly infamous for me) series of Two Sum, with its part 2. Well, we don’t have the luxury of hash maps here, but we do have a sorted array. That makes me itch for applying binary search.

Its not straight forward binary search, as you don’t clearly see a left, mid, right and don’t have a clue how you shorten the array in half (Spoilers: You Don’t). But, if you just put down the structure of Binary Search and superimpose the problem on top of it, it becomes evident that this question indeed does use the skeleton of Binary Search wrapping around Two Pointers (Who would have thought!)

Your left takes care of getting the number from start of the array, right for the end and mid is basically the sum.

• If your sum is less than target -> Move left inwards by 1
• If your sum is more than target -> Move right inwards by 1
• If equal, return indexes

Approach

Now for the approach:

1. Initialise left as 0
2. Initialise right as Array length
3. WHILE(left>right):
        Calculate sum
        IF(sum < target):
            move left by 1
        ELSE IF(sum > target):
            move right by 1
        ELSE
            return indexes of numbers

Complexity

• Time complexity: O(N)

Since this doesn’t actually use Binary Search its not O(logN). Every step is a decrement by one so it will iterate over the entire array once.

• Space complexity: O(1)

Code

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left<right:
            sums = numbers[left]+numbers[right]
            if sums == target:
                return left+1,right+1
            elif sums > target:
                right = right - 1
            else:
                left = left + 1

I did try to apply binary search and play with mid (but, looks like I need more coffee to figure out how to do it that way, but it is possible)
Also, python because easy to read and write.

P.S. If you found this useful, please share your support with comments and claps. If you feel this can be useful to someone you know, please feel free to share this publication and story. Join my journey on DSA on my github where I am journaling all the questions I have solved and commented on: StrugglingCOderDSA.

Cheers,
Your Struggling COder;