Cracking the LeetCode Two Sum Variations - All 5 Problems
Original Two Sum Problem
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
1Example 1:
2Input: nums = [2,7,11,15], target = 9
3Output: [0,1]
4Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
5
6Example 2:
7Input: nums = [3,2,4], target = 6
8Output: [1,2]
9
10Example 3:
11Input: nums = [3,3], target = 6
12Output: [0,1]
Brute Force
1class Solution:
2 def twoSum(self, nums: List[int], target: int) -> List[int]:
3 n = len(nums)
4 for i in range(n):
5 for j in range(i+1, n):
6 if nums[i] + nums[j] == target:
7 return [i, j]
Time complexity: O(n^2); n is the length of the input array. Space complexity: O(1); as we are only using a few extra variables and not using any extra data structures to store intermediate results.
Optimized
1class Solution:
2 def twoSum(self, nums: List[int], target: int) -> List[int]:
3
4 num_map = {} # put numbers as key and index as values
5 # Enumerate through the list 'nums'. 'enumerate' gives us an
6 # index (idx) and the item at that index (num)
7 # For example, if nums = [2, 7, 11, 15],
8 # after this loop, num_map = {2: 0, 7: 1, 11: 2, 15: 3}
9 for idx, num in enumerate(nums):
10 # key: value = number, index
11 num_map[num] = idx
12
13 for idx, num in enumerate(nums):
14 # Calculate the complement of the current number
15 # (i.e., the difference between 'target' and this number).
16 com = target - num
17 # If the complement exists in the dictionary 'num_map'
18 # and it's not the current number...
19 if com in num_map and idx != num_map[com]:
20 return [idx, num_map[com]]
Time Complexity: O(n); The code includes a single loop that iterates over the entirety of the input array 'arr' (where 'n' is the length of 'arr'). The operations within this loop - dictionary lookups and updates - each have a constant time complexity of O(1). Therefore, the overall time complexity remains linear, i.e., O(n).
Space Complexity: O(n); The code uses a dictionary to store the indices of all elements in the input array 'arr'. Since the size of this dictionary directly scales with the size of the input array 'arr', the space complexity is O(n).
Variant 1: Data Structure Design
This is a LeetCode premium problem.
Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value.
1For example,
2add(1); add(3); add(5);
3find(4) -> true
4find(7) -> false
1class TwoSum:
2 def __init__(self):
3 self.numbers = []
4
5 def add(self, number):
6 self.numbers.append(number)
7
8 def find(self, target):
9 seen = set()
10 for num in self.numbers:
11 complement = target - num
12 if complement in seen:
13 return True
14 seen.add(num)
15 return False
Variant 2 - Two Sum II - Input Array Is Sorted
Given a 1-indexed array of integers numbers that is already *sorted in non-decreasing order*, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
1Input: numbers = [2,7,11,15], target = 9
2Output: [1,2]
3Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
1Input: numbers = [2,3,4], target = 6
2Output: [1,3]
3Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
1class Solution:
2 def twoSum(self, numbers: List[int], target: int) -> List[int]:
3 left, right = 0, len(numbers) - 1
4 while left < right:
5 current_sum = numbers[left] + numbers[right]
6 if current_sum > target:
7 right -= 1
8 elif current_sum < target:
9 left += 1
10 else:
11 return [left + 1, right + 1]
Variant 3 - Two Sum Less Than K
This is a LeetCode premium problem.
Given an array A of integers and integer K, return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K. If no i, j exist satisfying this equation, return -1.
1Example 1:
2Input: A = [34,23,1,24,75,33,54,8], K = 60
3Output: 58
4Explanation:
5We can use 34 and 24 to sum 58 which is less than 60.
6
7Example 2:
8Input: A = [10,20,30], K = 15
9Output: -1
10Explanation:
11In this case it's not possible to get a pair sum less that 15.
Brute Force
1# comparing all pairs
2def max_sum_less_than_k(A, K):
3 n = len(A)
4 max_sum = -1
5
6 for i in range(n):
7 for j in range(i + 1, n):
8 current_sum = A[i] + A[j]
9 if current_sum < K and current_sum > max_sum:
10 max_sum = current_sum
11
12 return max_sum
Time complexity: O(n^2)
Space complexity: O(1)
Optimized
1# using two pointers
2def max_sum_less_than_k(A, K):
3 A.sort() # sort the array in ascending order
4 n = len(A)
5 max_sum = -1
6 left = 0 # pointer starting from the left
7 right = n - 1 # pointer starting from the right
8
9 while left < right:
10 current_sum = A[left] + A[right]
11 if current_sum < K:
12 # # update max_sum if necessary
13 max_sum = max(max_sum, current_sum)
14 # move the left pointer to the right
15 # so that we can make larger sum
16 left += 1
17 else:
18 # move the right pointer to the left
19 right -= 1
20
21 return max_sum
Time complexity: O(n log n) due to the initial sorting step.
Space complexity: O(1)
Author: Sadman Kabir Soumik