3 of 26

LeetCode: Find the First and Last Position of Element in a Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

4 of 26

Find First and Last (C++ Code, no library) 1/2

vector<int> searchRange(vector<int>& nums, int target) {

vector<int> ans(2,-1); // int[] ans = new int[]{-1,-1};

int b = 0, e = nums.size()-1;

if (e == -1 || nums[b]>target || nums[e]<target) return ans;

// invariance: nums[b-1]<target && nums[e]>=target

while (b < e) { // find first occurrence

int m = b + (e-b)/2; // (b+e)/2 may overflow in rare cases

if (nums[m] < target) { b = m+1; }

else if (nums[m]==target && m==b) {

b = m; break; // found m

} else { e = m; }

}

if (nums[b] != target) return ans;

Condition is complicated because we want first appearance.

Necessary for invariance

Performance optimization

5 of 26

Find First and Last (C++ Code, no library) 2/2

e = nums.size() - 1;

ans[0] = b; ans[1] = e;

if (nums[e] == target) return ans;

// invariance: nums[b]==target & nums[e]>target

while (b < e-1) { // find last occurrence

int m = b + (e-b)/2;

if (nums[m] > target) { e = m; }

else { b = m; }

}

ans[1] = b;

return ans;

6 of 26

Suggestion for Writing Binary Search

Have a clearly-specified invariance.

Ensure that it is true at the beginning of the iteration.
Ensure that any update within the loop maintains the invariance.

Ensure that the loop makes progress.

Depending on the loop condition and update, it is possible to have an infinite loop.

7 of 26

Find First and Last (C++ Code, using library)

vector<int> searchRange(vector<int>& nums, int target) {

vector<int> ans(2,-1);

if (nums.size() == 0) return ans;

vector<int>::iterator low,up;

// Returns an iterator pointing to the first element that does not compare less than target

low = lower_bound (nums.begin(), nums.end(), target);

if (low == nums.end() || *low != target) return ans;

// Returns an iterator pointing to the first element which compares greater than val

up = upper_bound (low, nums.end(), target);

ans[0] = low - nums.begin();

ans[1] = up - nums.begin() - 1;

return ans;

}

Can we solve this in Java using binarySearch?

8 of 26

Find First and Last (What if Java is Used?)

Java has Arrays.binarySearch(...[] array, …)

If array is not sorted, the result is undefined.
Returns index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1).
The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key.
If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

Cannot solve this problem.

9 of 26

Binary Search Example Problem 2:

LeetCode: Find Peak Element

10 of 26

LeetCode: Find Peak Element

A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks; return any one is fine.

Input: nums = [1,2,3,1] Output: 2

Explanation: 3 is a peak element with index 2.

Input: nums = [3,2,1,3,5,6,4] Output: 0 or 5

11 of 26

Find Peak Element Analysis

A linear scan with complexity O(N) works
How to speed it up?
Take a look at the middle element, if it is greater than both neighbors, then it is a peak.
What do you know about peaks if it is less than its right neighbor?

[3,2,1,3,5,6,4]

There must exist a peak to the right of the middle element!

Proof. Either the right neighbor is a peak; or it is less than its right neighbor. If the sequence keeps increasing, the rightmost element is a peak.

Can be solved by binary search.

12 of 26

Lesson on Binary Search

Understand the binary search API of your language.
Know how to write your own binary when you need to do so.
Write down the invariance as a comment.
Sometimes, it may not be obvious that binary search is the solution.
Binary search can also be used for one class of optimization problems (will be covered in CP2).

13 of 26

Meet-in-the-Middle Problem 1:

LeetCode: 3 Sum Closest

14 of 26

Warmup

LeetCode: Two Sum: Given an array of integers, return indices of the two numbers such that they add up to a specific target T.
LeetCode: Two Sum II - Input Array is Sorted: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
LeetCode: 3Sum: Given an array nums of n integers, find all unique elements a, b, c in nums such that a + b + c = 0?

15 of 26

LeetCode: 3 Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Input: nums = [-1, 2, 1, -4], target = 1 Output: 2

Closest 3sum is 2 = -1 + 2 + 1

16 of 26

3Sum Closest Analysis

Bruteforce takes time O(N^3)
O(N^2) solution exist. First sort the array. Then loop over all possibilities for the first of the three elements, then solve 2Sum closest in linear time.
How to solve 2Sum closest in linear time when sorted?
Use two pointers

If A[b] + A[e] < target, b++
If A[b] + A[e] > target, e--

17 of 26

C++ Code for 3Sum Closest

int threeSumClosest(vector<int>& nums, int target) {

sort(nums.begin(), nums.end());

int n = nums.size(), bestgap = INT_MAX, bestsum;

for(auto t=nums.begin(); t<nums.end()-2; ++t) {

auto be = t+1, en = nums.end()-1;

int nt = target - *t;

while (be < en) {

int res = *be + *en, ngap = abs(res - nt);

if (ngap < bestgap) { bestgap = ngap;

bestsum = *be + *en + *t; }

if (res < nt) be++;

else if (res > nt) en--;

else return target;

}

return bestsum;

}

1 2

2 3

3 4

4 5

5 6

100

18 of 26

C++ Code for 3Sum Closest (Another version)

int threeSumClosest(vector<int>& nums, int target) {

sort(nums.begin(), nums.end());

int n = nums.size(), bestgap = INT_MAX;

for(int i=0; i<n-2; i++) {

int be = i+1, en = n-1;

while (be < en) {

int gap = nums[be] + nums[en] + nums[i] - target;

if (abs(gap) < abs(bestgap)) bestgap = gap;

if (gap < 0) be++;

else if (gap > 0) en--;

else return target;

}

return target + bestgap;

}

19 of 26

Meet-in-the-Middle Problem 2:

LeetCode: 4Sum II

20 of 26

LeetCode: 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. All A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2²⁸ to 2²⁸ - 1.

Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]

Output: 2

The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

21 of 26

4Sum II Analysis

Bruteforce takes time O(N^4)
How to solve this in O(N^3)?
Sort two of the arrays. Loop over all (N^2) combinations of the other two arrays, use two pointers over the two sorted arrays.
Can we solve this in O(N^2)?
Yes, by using O(N^2) extra memory to store all possible sums from two arrays. (This is meet-in-the-middle.)

22 of 26

4SUM II (Code in Java)

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

HashMap<Integer,Integer> ab = new HashMap<Integer,Integer>();

for (int x : A) for (int y : B)

ab.merge(x+y, 1, Integer::sum);

int ans = 0;

for (int x : C) for (int y : D)

ans += ab.getOrDefault(-(x+y), 0);

return ans;

}

23 of 26

2SUM to 4SUM

	Exact sum	Nearest sum (strictly harder than exact sum)
2 SUM	O(N) time O(N) memory Using HashSet Or method for nearest sum.	O(N log N) time O(1) extra memory Sorting plus 2 pointers
3 SUM	Best method is that for nearest sum.	O(N^2) time O(1) extra memory Sort two arrays. Iterate over the third, 2 pointer over the two sorted arrays
4 SUM	O(N^2) time O(N^2) memory Store pair sums over 2 arrays in HashSet.	O(N^2 logN) time O(N^2) memory Use two arrays to store pair-wise sums, sort them, and then 2 pointers

What is the complexity for 5SUM, 6SUM, etc?

24 of 26

Meet-in-the-Middle Example 3:

Maximum Subset Sum

25 of 26

Maximum Subset Sum: Problem

Given a set of n integers where n <= 40. Each of them is at most 10¹², find the maximum subset sum less than or equal to S where S <= 10¹⁸.

Input : set[] = {38, 34, 18, 12, 6, 5} and S = 42

Output : 41, which is sum of {18, 12, 6, 5}

Bruteforce takes time 2⁴⁰, which is not fast enough. If the n integers are small, one can use dynamic programming, but here numbers are too large.

26 of 26

Maximum Subset Sum: Analysis

Split the set of integers into 2 subsets say A and B. A having first n/2 integers and B having rest.
Find all possible subset sums of integers in set A and store in an array X. Sort it.
Using 2^n/2 memory to speed up searching.
Enumerate all subsets of B and then find the element in X that achieves maximum sub below S.
To enumerate all subsets of an n-element set, one way is to enumerate from integers from 0 to 2^n-1 and interpret each bit as whether an element is included or not.