# Handy Hacks #1: LeetCode Weekly Contest 222

# Weekly Contest 222

### Question 1:

- Greedy choice
- Easy way to sort vectors:

Here the inputs are of the form [[2,5],[4,7],[3,9]] and we need to sort it based on the descending order of 2nd value in each pair. ie, it should become [[3,9],[4,7],[2,5]]

```
sort(a.begin(), a.end(),
[](const auto& L, const auto& R){
return L[1] > R[1];
}
);
```

### Question 2:

- 1<<21 means 2 power 21 (bit shift)
- Read the constraints properly. In this question deliciousness[i] can vary from 0 to 2^20 meaning -> sum of 2 elements in array can at max have value = 2^20+2^20 = 2^21.

```
ALGORITHM:
1. insert all elements of deliciousness into map[]
2. go to every element in deliciousness[]
loop over all possible sums from 1 to 2^21
if sum-element is present in map
if element==sum-element
contribution=number of deliciousness[sum-element] in map - 1
else
contibution = number of deliciousness[sum-element] in map
3. Answer will be contribution/2
```

- [1,1,1,3,3,3,7] would be {1:3,3:3,7:1} in map. For a sum=8, (1,7) can form 3 pairs. Each time we encounter a 1 or a 7, we add it's pair's frequency = 1+1+1 + 3 = 6. We would have counted each (1,7) twice by then. So we need to divide by 2 in the end.

### Question 3:

- Binary Search Application
Construct a prefix sum array and we need to split it into 3 parts - left, mid and right

`prefix[left]<=prefix[right]-prefix[left]<=prefix[n-1]-prefix[right] 2*prefix[right]<=prefix[n-1]+prefix[left]`

```
ALGORITHM:
1. ans=0
2. For every index left in the prefix sum array
3. leftsum=prefix[left]
4. remainingsum=(prefix[n-1]-leftsum)/2
5. we need to satisfy 2*prefix[left]<=prefix[right]
we also need prefix[right]<=(prefix[n-1]+prefix[left])/2
left+1 is starting index of mid part of array
right is ending index of mid part of array
6. For range in [left+1,n-1]
it1=first index with prefix sum >= 2*prefix[left]
it2=first index with prefix sum > (prefix[n-1]+prefix[left])/2
so all indices between it1 and it2 will satisfy our conditions!!!
ans+=(it2-it1)
7. return ans
```

lower_bound and upper_bound are great functions which can help!

`Iterator lower_bound (Iterator first, Iterator last, const val)`

- lower_bound will return first index with value>=val
- upper_bound will return first index with value>val

### Question 4

- If we can find
**longest common subsequence**between target[] and arr[]; we just need to add the elements in target[] (which are not part of LCS) to arr[] to make target[] a subsequence of arr[]`Answer is target.size() - LCS.size()`

- We could use normal approach of finding LCS using dp to get answer but it will result in TLE due to the length constraints.
- They have specified elements of target are distinct. This is a
*green light*to convert problem into**Longest Increasing Subsequence**.`To convert LCS->LIS (since target[] are distinct); create a Map from target[i] to i if any element of arr[] is present in target[] push the index of element in target[](Map[arr[i]]) to a vector`

- Now the vector would contain indices - for it to be a longest common subsequence we would need to choose indices in the increasing order -> becomes a longest increasing subsequence problem.
- This can be solved by creating a new vector - lets say vector LIS
`we traverse through all elements of the indices vector: we check if there exists any number in LIS which is just greater than/equal to current element if yes, replace that number with current element if no, push current element into LIS`

- Now, LIS would have the - LIS ðŸ˜‚

Good luck on your next contest!

Until next time, @stratospher

Â

Â

## No Comments Yet