# Arrays and Strings and HashMap(?)

**ArrayList **-> An array that resizes itself when still needed while still providing O(1) access. A typical implementation is that when the array is full, the array doubles in size. Each doubling takes O(n) time, but happen rarely that its armortized insertion time is O(1).

**StringBuilder**

StringBuilder is a beneficial class in Java for constructing and manipulating strings efficiently. Here are some benefits of using wordStringBuilder:

- Improved performance: Unlike String objects, which are immutable, StringBuilder objects are mutable, which means you can modify them without creating a new object. Thisro can improve performance when building or modifying strings because it avoids the overhead of creating multiple intermediate String objects.form
- Efficient memory usage: When you use String concatenation using the ‘+’ operator, a new String object is created each time, which can quickly consume memory if done frequently. With StringBuilder, you can append new characters or strings to an existing StringBuilder object, which reduces memory usage.
- Flexible and easy to use: StringBuilder provides methods for appending, inserting, deleting, and replacing characters and strings in a flexible and easy-to-use way. This makes it easy to manipulate strings and build them up incrementally.

Overall, StringBuilder is a useful class for constructing and manipulating strings in a performant and memory-efficient way, and it is a good choice when dealing with larger or more complex string manipulations.

`StringBuilder sb = new StringBuilder("abc").append("de");`

String str = sb.toString();

// Append a string

sb.append(" She sells sea shells by the sea shore.");

// Insert a string at a specific index

sb.insert(45, "quick ");

// Delete a range of characters

sb.delete(30, 34); // Removes "jumps"

// Replace a string with another string

sb.replace(49, 52, "smiles");

Array -> 数组

Contiguous subarray -> 直数组

Element -> 元素

Sum -> 合, eg, 它们的合是。。。 Their sum is

右边端点，左边端点 Left index, right index

# Common Techniques

## Sliding Window Approach

A window is formed over some part of the data and this window can slide over the data to capture different portions of it. When a window slides, only two elements change. The oldest one drops off and the newest one comes into the frame.

In the brute force approach, the inefficient part is that for any two consecutive subarrays of size k, the overlapping part (which contains k-1 elements) is evaluated twice. By using the sliding window approach, we can get rid of that and calculate the sum in O(1) using the sum of previous consecutive subarray.

You can also implement the sliding window approach with two pointers left & right as the following code.

The time complexity is then linear O(n) as we only need one loop.

`left = 0`

right = 0

while right < n:

window.add(s[right])

right += 1

while (condition):

window.remove(s[left])

left += 1

**Creating a character array to keep track of the occurrences of each character**

`int[] counter(String word) {`

int[] count = new int[26];

for (char c : word.toCharArray()) count[c - 'a']++;

return count;

}

## Counting inversions

Use Merge sort

# Leetcode 775

775. Global and Local Inversions

You are given an integer array `nums`

of length `n`

which represents a permutation of all the integers in the range `[0, n - 1]`

.

The number of **global inversions** is the number of the different pairs `(i, j)`

where:

`0 <= i < j < n`

`nums[i] > nums[j]`

The number of **local inversions** is the number of indices `i`

where:

`0 <= i < n - 1`

`nums[i] > nums[i + 1]`

Return `true`

*if the number of **global inversions** is equal to the number of *** local inversions**.

**Example 1:**

`Input: nums = [1,0,2]`

Output: true

Explanation: There is 1 global inversion and 1 local inversion.

**Example 2:**

`Input: nums = [1,2,0]`

Output: false

Explanation: There are 2 global inversions and 1 local inversion.

`class Solution {`

public boolean isIdealPermutation(int[] nums) {

// local: Compare to the one next to you

// global: Compare to the list of nums on your right

int local = computeLocal(nums);

int global = computeGlobal(nums);

return local == global;

}

public int computeGlobal(int[] nums){

return mergeSort(nums, 0, nums.length-1);

}

public int mergeSort(int[] nums, int start, int end){

int count = 0;

if(start < end){

int mid = (start+end)/2;

count = mergeSort(nums, start, mid);

count += mergeSort(nums, mid+1, end);

count += merging(nums, start, mid+1, end);

}

return count;

}

public int merging(int[] nums, int start, int mid, int end){

int[] copy = new int[nums.length];

for(int k=start; k<=end; k++){

copy[k] = nums[k];

}

int count = 0;

int i=start;

int j=mid;

int idx=start;

while(i<mid && j<=end){

if(copy[i]<=copy[j]){

nums[idx]=copy[i];

i++;

} else {

nums[idx]=copy[j];

j++;

count+=(mid-i);

}

idx++;

}

while(i<mid){

nums[idx]=copy[i];

idx++;

i++;

}

while(j<=end){

nums[idx]=copy[j];

j++;

idx++;

}

return count;

}

public int computeLocal(int[] nums){

int count = 0;

for(int i=1; i<nums.length; i++){

if(nums[i] < nums[i-1]) count++;

}

return count;

}

}

// Time limit exceeded..

Accepted solution

## Approach #2: Remember Minimum [Accepted]

**Intuition**

In performing a brute force, we repeatedly want to check whether there is some `j >= i+2`

for which `A[i] > A[j]`

. This is the same as checking for `A[i] > min(A[i+2:])`

. If we knew these minimums `min(A[0:]), min(A[1:]), min(A[2:]), ...`

we could make this check quickly.

**Algorithm**

Let’s iterate through `A`

from right to left, remembering the minimum value we've seen. If we remembered the minimum `floor = min(A[i:])`

and `A[i-2] > floor`

, then we should return `False`

. This search is exhaustive, so if we don't find anything after iterating through `A`

, we should return `True`

.

`public boolean isIdealPermutation(int[] A) {`

int N = A.length;

int floor = N;

for (int i=N-1; i>=2; --i) {

floor = Math.min(floor, A[i]);

if (A[i-2] > floor) return false;

}

return true;

}

**Complexity Analysis**

- Time Complexity: O(N), where N is the length of
`A`

. - Space Complexity: O(1).

TODO: https://leetcode.com/problems/reverse-pairs/

## 315. Count of Smaller Numbers After Self

This is one of those questions that are simple enough to give you hope but are actually an omega pain in the butt

You are given an integer array *nums* and you have to return a new *counts* array. The *counts* array has the property where `counts[i]`

is the number of smaller elements to the right of `nums[i]`

.

**Example 1:**

**Input:** nums = [5,2,6,1]

**Output:** [2,1,1,0]

**Explanation:**

To the right of 5 there are **2** smaller elements (2 and 1).

To the right of 2 there is only **1** smaller element (1).

To the right of 6 there is **1** smaller element (1).

To the right of 1 there is **0** smaller element.

The optimal solution is to use MergeSort method to count.

We make use of 2 additional variables to help us. The first is int **count**[] which stores the result. The second is **rightCount **inside the merge method to help us in tracking number of right elements that is smaller than the current left element we are iterating.

QNS: What does int[] **indexes** mean?

Note that in merge, the items in the positions from [start…mid] and [mid+1…end] are already sorted internally. We term these two sorted portions to be LEFT and RIGHT.

In this merging, we are iterating through the indexes array. The p1, p2…indexes are the indexes of the elements in the LEFT and RIGHT respectively. We compare the values at those indexes p1, p2.

Here, we need to track its’ indexes and add to the new array depending on the values of these indexes (Doing merge sort on the index array and the basis of comparison is their values). We want to track the indexes because we need to edit count[] array.

** TDLR: We are only modifying the values in the indexes array. nums array remains unchanged.

Each time we add an element from the left side, we set the **count[i]** to be **rightCount**.

**rightCount **contains the number of elements on the right that is smaller than this current element on the left.

`class Solution {`

int[] count;

public List<Integer> countSmaller(int[] nums) {

List<Integer> res = new ArrayList<>();

count = new int[nums.length];

int[] indexes = new int[nums.length];

for(int i=0; i<nums.length; i++){

indexes[i]=i;

}

mergeSort(nums, indexes, 0, nums.length-1);

for(int i=0; i<count.length; i++){

res.add(count[i]);

}

return res;

}

public void mergeSort(int[] nums, int[] indexes, int start, int end){

if(start<end){

int mid = (start+end)/2;

mergeSort(nums, indexes, start, mid);

mergeSort(nums, indexes, mid+1, end);

merging(nums, indexes, start, mid+1, end);

}

}

// sort the index.....

// We want to know which index ends up in which position eventually.

public void merging(int[] nums, int[] index, int start, int mid, int end){

int i=start;

int j=mid;

int idx=0;

int rightCount = 0;

int[] newIndexes = new int[end-start+1];

// index[i] gives the original index of the number at i.

while(i<mid && j<=end){

// right smaller than left,

// index of current val will be moved leftward -> to indicate its' new position

if(nums[index[j]] < nums[index[i]]){

newIndexes[idx] = index[j];

rightCount++;

j++;

idx++;

} else {

// left smaller than right.

// This current number is bigger than all those numbers that were previously moved from right

// to left...hence the inversion count (rightcount) should be added to this particular number.

newIndexes[idx] = index[i];

count[index[i]] += rightCount;

i++;

idx++;

}

}

while(i<mid){

newIndexes[idx] = index[i];

count[index[i]] += rightCount;

idx++;

i++;

}

while(j<=end){

newIndexes[idx] = index[j];

idx++;

j++;

}

for(int k=start; k<=end; k++){

index[k] = newIndexes[k-start];

}

}

}

## Explanation from the LEETCODE (This is so confusing, i don’t really understand)

**Intuition**

Prerequisite: Merge Sort

If you are not familiar with Merge Sort, you should check relevant tutorials before continuing.

Also, here is a basic application of Merge Sort that you can practice on:Sort an Array

To apply merge sort, one key observation is that:

The smaller elements on the right of a number willjump from its right to its leftduring the sorting process.

`class Solution {`

public List<Integer> countSmaller(int[] nums) {

int n = nums.length;

int[] result = new int[n];

int[] indices = new int[n]; // record the index. we are going to sort this array

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

indices[i] = i;

}

// sort indices with their corresponding values in nums, i.e., nums[indices[i]]

mergeSort(indices, 0, n, result, nums);

// change int[] to List to return

List<Integer> resultToReturn = new ArrayList<Integer>(n);

for (int i : result) {

resultToReturn.add(i);

}

return resultToReturn;

}

private void mergeSort(int[] indices, int left, int right, int[] result, int[] nums) {

if (right - left <= 1) {

return;

}

int mid = (left + right) / 2;

mergeSort(indices, left, mid, result, nums);

mergeSort(indices, mid, right, result, nums);

merge(indices, left, right, mid, result, nums);

}

private void merge(int[] indices, int left, int right, int mid, int[] result, int[] nums) {

// merge [left, mid) and [mid, right)

int i = left; // current index for the left array

int j = mid; // current index for the right array

// use temp to temporarily store sorted array

List<Integer> temp = new ArrayList<Integer>(right - left);

while (i < mid && j < right) {

if (nums[indices[i]] <= nums[indices[j]]) {

// j - mid numbers jump to the left side of indices[i]

result[indices[i]] += j - mid;

temp.add(indices[i]);

i++;

} else {

temp.add(indices[j]);

j++;

}

}

// when one of the subarrays is empty

while (i < mid) {

// j - mid numbers jump to the left side of indices[i]

result[indices[i]] += j - mid;

temp.add(indices[i]);

i++;

}

while (j < right) {

temp.add(indices[j]);

j++;

}

// restore from temp

for (int k = left; k < right; k++) {

indices[k] = temp.get(k - left);

}

}

}

Let N be the length of `nums`

.

- Time Complexity: O(Nlog(N)). We need to perform a merge sort which takes
*O*(*N*log(*N*)) time. All other operations take at most O(N) time. - Space Complexity: O(N), since we need a constant number of arrays of size O(N).

# Heap Sort

# Leetcode

## 27. Remove Element

Given an array *nums* and a value *val*, remove all instances of that value **in-place** and return the new length.

Do not allocate extra space for another array, you must do this by **modifying the input array ****in-place** with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Return the last index of the modified array.

**Example 1:**

**Input:** nums = [3,2,2,3], val = 3

**Output:** 2, nums = [2,2]

**Explanation:** Your function should return length = **2**, with the first two elements of *nums* being **2**.

It doesn't matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,3,0,0], your answer will be accepted.

**Example 2:**

**Input:** nums = [0,1,2,2,3,0,4,2], val = 2

**Output:** 5, nums = [0,1,4,0,3]

**Explanation:** Your function should return length = **5**, with the first five elements of *nums* containing **0**, **1**, **3**, **0**, and **4**. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.

## Leetcode 53. Q1 Given an array of integers, return the highest sum of any **k** consecutive elements in the array.

Wanted to use sliding window…but didn’t come up with a solution. So in the end, decide to use dynamic programming.

To remember how to solve this question, think of the sub problem:

- If i have the max sum of k consecutive elements from 0…i-1, and i am currently at index i, how do i make use of the results from prior? To form dp[i], how do i make use of dp[i-1]
- The first way we might think of is to have the 1D array,
**dp[i-1] contain the max sum of K consecutive elements from 0…...i–1,**then decide whether to add curr element arr[i] to it or not. However, we soon realise that the element arr[i-1] might not have been included in the sum of dp[i-1].**Only when the previous element arr[i-1] has been added to dp[i-1], we can add arr[i] into the dp[i], otherwise it is not consecutive.** - Hence, we need a way to make it 100% correct for us to decide whether to add current element to dp[i].
- We then change our definition of what dp[i-1] contains.
- One way is to set the condition that
**dp[i-1] will always contain the maximum sum of elements from position i-1**(Ensure that the prev element is always added to the sum)**to somewhere ≥ 0.**Hence, in each iteration we are safe to append arr[i] to the sum of dp[i].**Then we can make it such that in each iteration, we are only deciding whether we want to add current element a[i] to dp[i-1] or start afresh with a[i]. We then have to keep track of the maximum sum by having a variable.**

`class Solution {`

public int maxSubArray(int[] nums) {

// at each index, you either include yourself to the prev or start a new count

// dp[i]: max sum up till i. including i.

int max = nums[0];

int[] dp = new int[nums.length];

Arrays.fill(dp, 0);

dp[0]=nums[0];

for(int i=1; i<nums.length; i++){

int addCurr = dp[i-1] + nums[i];

int dontAdd = nums[i];

if(addCurr > dontAdd){

max = Math.max(addCurr, max);

dp[i]=addCurr;

} else {

dp[i]=dontAdd;

max = Math.max(dontAdd, max);

}

}

return max;

}

}

## Q2 Given a string, find the length of the longest substring without repeating characters.

Approach 1: Naive brute force where you try every combination of substrings

Approach 2: Optimised brute force. For each starting index i, find the longest substring. O(n)*O(n)=O(n²)

Approach 3:

Can use HashMap

Hard question…i could not figure out how to do the hashmap method as suggested by huahua. Spent a good hour trying and failing…then I copied this solution below from youtube….my brain just isnt working…

currSubstring.substring(1); // Means only keep characters after the first.

`// 2023: Most recent attempt`

class Solution {

public int lengthOfLongestSubstring(String s) {

// Sliding window

if (s.length()==0) return 0;

HashSet<Character> set = new HashSet<>();

int max = 1;

int start=0;

int end=0;

while(start<=end && end<s.length()){

if(set.contains(s.charAt(end))){

set.remove(s.charAt(start));

start++;

} else {

set.add(s.charAt(end));

max = Math.max(max, set.size());

end++;

}

}

return max;

}

}

# 340. Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

**Example 1:**

`Input: s = "eceba", k = 2`

Output: 3

Explanation: The substring is "ece" with length 3.

**Example 2:**

`Input: s = "aa", k = 1`

Output: 2

Explanation: The substring is "aa" with length 2.

`class Solution {`

public int lengthOfLongestSubstringKDistinct(String s, int k) {

HashSet<Character> set = new HashSet<>();

HashMap<Character, Integer> setCount = new HashMap<>();

int max = 1;

int start = 0;

int end = 0;

if (k==0) return 0;

while(start<=end && end<s.length()){

Character curr = s.charAt(end);

set.add(curr);

int cnt = setCount.getOrDefault(curr, 0);

setCount.put(curr, cnt+1);

while(set.size() > k){

// remove

Character charToRemove = s.charAt(start);

if (set.contains(charToRemove)){

int currCount = setCount.get(charToRemove);

if (currCount == 1){

set.remove(charToRemove);

}

setCount.put(charToRemove, currCount-1);

start++;

}

}

max = Math.max(max, end-start+1);

end++;

}

return max;

}

}

# LEETCODE 1423 Maximum Points You Can Obtain from Cards

There are several cards **arranged in a row**, and each card has an associated number of points. The points are given in the integer array `cardPoints`

.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly `k`

cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array `cardPoints`

and the integer `k`

, return the *maximum score* you can obtain.

**Example 1:**

`Input: cardPoints = [1,2,3,4,5,6,1], k = 3`

Output: 12

Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

**Example 2:**

`Input: cardPoints = [2,2,2], k = 2`

Output: 4

Explanation: Regardless of which two cards you take, your score will always be 4.

**Example 3:**

`Input: cardPoints = [9,7,7,9,7,7,9], k = 7`

Output: 55

Explanation: You have to take all the cards. Your score is the sum of points of all cards.

`class Solution {`

public int maxScore(int[] cardPoints, int k) {

int[] front = new int[cardPoints.length+1]; // front[i] represents the sum of cards if we take i cards from the start

int[] end = new int[cardPoints.length+1]; // end[i] represents the sum of cards if we take i cards from the end

// index 0 -> Take no card, hence is 0 by default

for(int i=1; i<=cardPoints.length; i++){

front[i] = front[i-1] + cardPoints[i-1];

end[i]=cardPoints[cardPoints.length-i]+end[i-1];

}

int max = 0;

int i=0;

while(i<=k){

max = Math.max(max, front[i] + end[k-i]);

i++;

}

return max;

}

}

`class Solution {`

public:

int maxScore(vector<int>& cardPoints, int k) {

if(k>cardPoints.size()) return 0;

vector<int> left;

int sum = 0;

left.push_back(0);

for(int i=0; i<cardPoints.size(); i++){

sum+=cardPoints[i];

left.push_back(sum);

}

vector<int> right;

right.push_back(0);

sum = 0;

for(int i=cardPoints.size()-1; i>=0; i--){

sum+=cardPoints[i];

right.push_back(sum);

}

int maxScore = 0;

for(int takeLeft=0; takeLeft<=k; takeLeft++){

maxScore = max(maxScore, left[takeLeft]+right[k-takeLeft]);

}

return maxScore;

}

};

# Two Sum: Given an array of integers, return **indices** of the two numbers such that they add up to a specific target.

## You may assume that each input would have *exactly* one solution, and you may not use the *same* element twice.

*exactly*

**Example:**

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,

return [0,1].

# Map<Integer, Integer> map = new HashMap<Integer, Integer>();

new int[] {1,2,3,4};

Need to be clear of what values you are storing in the Map.

# 167. 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:**

`Input: numbers = [2,7,11,15], target = 9`

Output: [1,2]

Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

**Example 2:**

`Input: numbers = [2,3,4], target = 6`

Output: [1,3]

Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

**Example 3:**

`Input: numbers = [-1,0], target = -1`

Output: [1,2]

Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Now, we need to make use of the property that it is sorted.

We use two indices, initially pointing to the first and the last element, respectively. Compare the sum of these two elements with `target`

. If the sum is equal to `target`

, we found the exactly only solution. If it is less than `target`

, we increase the smaller index by one. If it is greater than `target`

, we decrease the larger index by one. Move the indices and repeat the comparison until the solution is found.

`class Solution {`

public int[] twoSum(int[] numbers, int target) {

int start=0;

int end=numbers.length-1;

while(start<end){

int sum = numbers[start] + numbers[end];

if(sum < target){

start++;

} else if (sum > target){

end--;

} else{

return new int[]{start+1, end+1};

}

}

return new int[0];

}

}

- Time complexity: O(n). The input array is traversed at most once. Thus the time complexity is O(n).
- Space complexity: O(1). We only use additional space to store two indices and the sum, so the space complexity is O(1).

# Leetcode 15 Three Sum: Given an array `nums`

of *n* integers, are there elements *a*, *b*, *c* in `nums`

such that *a* + *b* + *c* = 0? Find all unique triplets in the array which gives the sum of zero.

**Note:**

The solution set must not contain duplicate triplets.

**Example:**

Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

Can make use of the two sum II function.

`class Solution {`

public List<List<Integer>> threeSum(int[] nums) {

Arrays.sort(nums);

List<List<Integer>> res = new ArrayList<>();

for (int i = 0; i < nums.length && nums[i] <= 0; ++i)

if (i == 0 || nums[i - 1] != nums[i]) {

twoSumII(nums, i, res);

}

return res;

}

void twoSumII(int[] nums, int i, List<List<Integer>> res) {

int lo = i + 1, hi = nums.length - 1;

while (lo < hi) {

int sum = nums[i] + nums[lo] + nums[hi];

if (sum < 0) {

++lo;

} else if (sum > 0) {

--hi;

} else {

res.add(Arrays.asList(nums[i], nums[lo++], nums[hi--]));

while (lo < hi && nums[lo] == nums[lo - 1])

++lo;

}

}

}

}

My initial solution

This solution does not pass the time-complexity..but i spent very long to come up with it so i shall keep it. It passes 311/313 test cases on leet code.

# Leetcode 16 Three sum closest

Given an integer array `nums`

of length `n`

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.

**Example 1:**

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

Output: 2

Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

**Example 2:**

`Input: nums = [0,0,0], target = 1`

Output: 0

Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

`class Solution {`

public int threeSumClosest(int[] nums, int target) {

int diff = Integer.MAX_VALUE;

int sz = nums.length;

Arrays.sort(nums);

for (int i = 0; i < sz && diff != 0; ++i) {

int lo = i + 1;

int hi = sz - 1;

while (lo < hi) {

int sum = nums[i] + nums[lo] + nums[hi];

if (Math.abs(target - sum) < Math.abs(diff)) {

diff = target - sum;

}

if (sum < target) {

++lo;

} else {

--hi;

}

}

}

return target - diff;

}

}

# 259. 3Sum Smaller (Premium)

Given an array of `n`

integers `nums`

and an integer `target`

, find the number of index triplets `i`

, `j`

, `k`

with `0 <= i < j < k < n`

that satisfy the condition `nums[i] + nums[j] + nums[k] < target`

.

**Example 1:**

`Input: nums = [-2,0,1,3], target = 2`

Output: 2

Explanation: Because there are two triplets which sums are less than 2:

[-2,0,1]

[-2,0,3]

**Example 2:**

`Input: nums = [], target = 0`

Output: 0

**Example 3:**

`Input: nums = [0], target = 0`

Output: 0

`// THIS SOLUTION IS WRONG...it doesn't take all the possible combinations because we never`

// update low...

class Solution {

List<List<Integer>> ls;

public int threeSumSmaller(int[] nums, int target) {

ls = new LinkedList<>();

Arrays.sort(nums);

for(int i=0; i<nums.length && nums[i]<target; i++){

if(i==0 || nums[i]!=nums[i-1]){

search(i, target, nums);

}

}

return ls.size();

}

public void search(int i, int target, int[]nums){

int low = i+1;

int high = nums.length-1;

while(low<high){

int sum = nums[i]+nums[low]+nums[high];

if(sum<target){

ls.add(Arrays.asList(i, low, high));

high--;

} else {

high--;

}

}

}

}

`// Second wrong attempt`

class Solution {

public int threeSumSmaller(int[] nums, int target) {

Arrays.sort(nums);

int result = 0;

for(int i=0; i<nums.length && nums[i]<target; i++){

if(i==0 || nums[i]!=nums[i-1]){

int count = search(i, target, nums);

System.out.println(count);

result+=count;

}

}

return result;

}

public int search(int i, int target, int[]nums){

int low = i+1;

int high = nums.length-1;

int rightMost = 0;

while(low<high && high<=nums.length-1){

int sum = nums[i]+nums[low]+nums[high];

if(sum<target){

rightMost = high;

high++;

} else {

high--;

}

}

return high==nums.length? high-low-1 : high-low;

}

}

Leetcode soln

`class Solution {`

public int threeSumSmaller(int[] nums, int target) {

Arrays.sort(nums);

int result = 0;

for(int i=0; i<nums.length-2; i++){

int count = search(nums, i+1, target-nums[i]);

result+=count;

}

return result;

}

public int search(int[] nums, int startIndex, int target){

int sum = 0;

for(int i=startIndex; i<nums.length; i++){

int largestEndIndex = binarySearch(nums, i, target-nums[i]);

sum+=largestEndIndex-i;

}

return sum;

}

// By the time we run this method, we would have already deducted 2 numbers from target.

public int binarySearch(int[] nums, int startIndex, int target){

int left = startIndex;

int right = nums.length-1;

int best = startIndex;

while(left<=right){

int mid = left + (right-left)/2;

if(nums[mid] < target){

best = mid;

left=mid + 1; // See if can go higher...

} else {

right=mid-1;

}

}

return best;

}

}

# Longest Common subsequence Leetcode 1143

Given two strings `text1`

and `text2`

, return the length of their longest common subsequence.

A *subsequence* of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A *common subsequence* of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

**Example 1:**

**Input:** text1 = "abcde", text2 = "ace"

**Output:** 3

**Explanation:** The longest common subsequence is "ace" and its length is 3.

**Example 2:**

**Input:** text1 = "abc", text2 = "abc"

**Output:** 3

**Explanation:** The longest common subsequence is "abc" and its length is 3.

**Example 3:**

**Input:** text1 = "abc", text2 = "def"

**Output:** 0

**Explanation:** There is no such common subsequence, so the result is 0.

The idea is to have 2D matrix where each index dp[i][j] represents the longest substring of the two strings: string1[0…..i] and string2[0…..j].

If you need to print out the string:

# Cracking the coding interview

## (1) Is Unique: Implement an algorithm to determine if a string has all unique characters. Cannot use additional data structures?

Approach 1: Brute Force 2 For Loop

Approach 2: Sorting O(nlogn)

Approach 3: Use of extra data structures O(n) -> Can use HashMap

Approach 4: Without extra data structure

## (2) Does string2 contains permutation of string1? (Leet code)

found this hard...spent 2 hours and in the end just gave up by looking at the solution.

Given two strings **s1** and **s2**, write a function to return true if **s2** contains the permutation of **s1**. In other words, one of the first string’s permutations is the **substring** of the second string.

**Example 1:**

**Input: **s1 = "ab" s2 = "eidbaooo"

**Output: **True

**Explanation:** s2 contains one permutation of s1 ("ba").

**Example 2:**

**Input: **s1= "ab" s2 = "eidboaoo"

**Output:** False

- Use sliding window approach here. The size of the window is length of string 1.
- Each time we iterate through String 2, we check if the count of characters for both are the same.

- Before line 11 is reached, the s1map and s2map will contain the mapping of the characters in both string 1 and a subset of string 2. Substring of length string 1 of string 2.
- Then we will have 2 maps called s1map and s2map.
- Afterwards, we immediately check whether they have the same values via matches function.
- Then, if it doesn’t match, we will go on to change the map of S2 by checking the next character of string2. For eg, if string1 is of length X and string2 is of length Y, then the next char to be explored will be at position (Y-X-1). This is line 14.
- In line 15, we will attempt to remove the first character of string2 at position 0.
- So everytime we check for similarity in the match function, we are keeping the size of the window to the length of string 1.

`class Solution {`

public boolean checkInclusion(String s1, String s2) {

HashMap<Character, Integer> s1Map = new HashMap<>();

HashMap<Character, Integer> s2Map = new HashMap<>();

if (s2.length() < s1.length()) return false;

for(int i=0; i<s1.length(); i++){

int count = s1Map.getOrDefault(s1.charAt(i), 0);

s1Map.put(s1.charAt(i), count+1);

int count3 = s2Map.getOrDefault(s2.charAt(i), 0);

s2Map.put(s2.charAt(i), count3+1);

}

for(int i=0; i<=s2.length()-s1.length(); i++){

String subStringOfS2 = s2.substring(i, i+s1.length());

// Remove prev

if (i>0){

int count2 = s2Map.getOrDefault(s2.charAt(i-1), 0);

if(count2 -1 == 0){

s2Map.remove(s2.charAt(i-1));

} else {

s2Map.put(s2.charAt(i-1), count2-1);

}

}

if (i>0){

// Add new

int count = s2Map.getOrDefault(subStringOfS2.charAt(subStringOfS2.length()-1), 0);

s2Map.put(subStringOfS2.charAt(subStringOfS2.length()-1), count+1);

}

if(compareHashMap(s1Map, s2Map)){

return true;

}

// compare hashmap of s1 and s2..if match just return true

}

return false;

}

public boolean compareHashMap(HashMap<Character, Integer> s1Map, HashMap<Character, Integer> s2Map){

for(Map.Entry<Character, Integer> entry: s1Map.entrySet()){

Character cc = entry.getKey();

int count = entry.getValue();

if(!s2Map.containsKey(cc)){

return false;

}

int s2Count = s2Map.get(cc);

if(s2Count!=count){

return false;

}

}

return true;

}

}

## (3) Leet Code 49 Group Anagrams

Given an array of strings, group anagrams together.

**Example:**

**Input:** ["eat", "tea", "tan", "ate", "nat", "bat"],

**Output:**

[

["ate","eat","tea"],

["nat","tan"],

["bat"]

]

First things to think of -> Use of Hash map

One correct solution is to set the key of the HashMap to be the sorted string of each anagram. For eg, if we have “cat”, “tac”, “cta”, the key of this group would be “act” which is the sorted version of those strings.

`char[] ca = eachString.toCharArray(); //Convert to array of characters`

Arrays.sort(ca) //Sort it;

String key = String.valueOf(ca); //Convert back to string format

Note that when we want to do integer, we do Integer.parseInt();

## (5) Leet Code 48 Rotate Image (Matrix)

You are given an *n* x *n* 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

**Note:**

You have to rotate the image **in-place**, which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

**Example 1:**

Giveninput matrix=

[

[1,2,3],

[4,5,6],

[7,8,9]

],rotate the input matrixin-placesuch that it becomes:

[

[7,4,1],

[8,5,2],

[9,6,3]

]

**Example 2:**

Giveninput matrix=

[

[ 5, 1, 9,11],

[ 2, 4, 8,10],

[13, 3, 6, 7],

[15,14,12,16]

], rotate the input matrixin-placesuch that it becomes:

[

[15,13, 2, 5],

[14, 3, 4, 1],

[12, 6, 8, 9],

[16, 7,10,11]

]

`//Another attempt in 2023`

class Solution {

public void rotate(int[][] matrix) {

int[] lines = new int[matrix.length*matrix[0].length];

int count = 0;

for(int row=0; row<matrix.length; row++){

for(int col=0; col<matrix[0].length; col++){

lines[count]=matrix[row][col];

count++;

}

}

int count2=0;

for(int col=matrix[0].length-1; col>=0; col--){

for(int row=0; row<matrix.length; row++){

matrix[row][col]=lines[count2];

count2++;

}

}

}

}

Leetcode solution

`class Solution {`

public void rotate(int[][] matrix) {

int n = matrix.length;

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

for (int j = 0; j < n / 2; j++) {

int temp = matrix[n - 1 - j][i];

matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];

matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i];

matrix[j][n - 1 - i] = matrix[i][j];

matrix[i][j] = temp;

}

}

}

}

`public void rotate(int[][] matrix){`

transpose(matrix);

reflect(matrix);

}

public void transpose(int[][] matrix){

int n = matrix.length;

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

for(int j=i+1; j<n; j++){

int tmp = matrix[i][j];

matrix[i][j] = matrix[j][i];

matrix[j][i] = tmp;

}

}

}

public void reflect(int[][] matrix){

int n = matrix.length;

int m = matrix[0].length;

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

for(int j=0; j<m/2; j++){

int temp = matrix[i][j];

matrix[i][j] = matrix[i][n-j-1];

matrix[i][n-j-1] = temp;

}

}

}

# (6) Leet Code 274 H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index *h* if *h* of his/her *N* papers have **at least** *h* citations each, and the other *N − h* papers have **no more than** *h* citations each.”

**Example:**

**Input:** citations = [3,0,6,1,5]

**Output:** 3

**Explanation: **[3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with **at least** 3 citations each and the remaining two with **no more than** 3 citations each, her h-index is 3.

**Note: **If there are several possible values for *h*, the maximum one is taken as the h-index.

`class Solution {`

public int hIndex(int[] citations) {

Arrays.sort(citations); //ascending

for(int i=citations.length-1; i>=0; i--){

int elmOnRight = citations.length-1-i;

if(elmOnRight >= citations[i]){

return elmOnRight;

}

}

return citations.length;

}

}

If the number of citation papers we have **seen** (excluding the current one) is bigger or equal to the** current h value,** then return the number of citation papers seen.

*See X papers, all must be at least **h** value — current. Compare number of X paper with h value. We want number of papers X to be ≥ **h**.*

**Leetcode answer (This is harder to understand, i prefer the one above)**

## Approach #1 (Sorting)

**Intuition**

Think geometrically. Imagine plotting a histogram where the y-axis represents the number of citations for each paper. After sorting in *descending* order, *h*-index is the length of the largest **square** in the histogram.

`public class Solution {`

public int hIndex(int[] citations) {

// sorting the citations in ascending order

Arrays.sort(citations);

// finding h-index by linear search

int i = 0;

while (i < citations.length && citations[citations.length - 1 - i] > i) {

i++;

}

return i; // after the while loop, i = i' + 1

}

}

# 275. H-Index II

Given an array of integers `citations`

where `citations[i]`

is the number of citations a researcher received for their `ith`

paper and `citations`

is sorted in **ascending order**, return *the researcher's h-index*.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of `h`

such that the given researcher has published at least `h`

papers that have each been cited at least `h`

times.

You must write an algorithm that runs in logarithmic time.

**Example 1:**

`Input: citations = [0,1,3,5,6]`

Output: 3

Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.

Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

**Example 2:**

`Input: citations = [1,2,100]`

Output: 2

`class Solution {`

public:

int hIndex(vector<int>& citations) {

int low = 0;

int high = citations.size()-1;

int best = -1;

int size = citations.size();

// We need to find the rightmost 'index' such that: (citations[index] <= n - index)

while(low<=high){

int mid = low + (high-low) / 2;

if(checkValid(citations, mid)){

best = max(citations[mid], best);

low = mid + 1; // can go higher?

} else {

best = max(best, size-mid); // the best number could be num of elements to the right of mid index

// eg, [0,0,4,4] -> best: 2

high = mid - 1; // need to go lower..

}

}

return best;

}

bool checkValid(vector<int>& citations, int index){

int val = citations[index];

int rightElementCount = citations.size()-index;

return rightElementCount >= val;

}

};

The fact that the algo must be in log time hints that we should use binary search.

## 7) Leet Code 150. Evaluate Reverse Polish Notation

Reverse polish notation -> **Postfix notation** in which operators follow their operands.

Polish notation ->** Operators precede their operands.**

The reverse Polish scheme was proposed in 1954 by Arthur Burks, Don Warren, and Jesse Wright[4] and was independently reinvented by Friedrich L. Bauer and Edsger W. Dijkstra in the early 1960s to reduce computer memory access and utilize the **stack** to evaluate expressions

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are `+`

, `-`

, `*`

, `/`

. Each operand may be an integer or another expression.

**Note:**

- Division between two integers should truncate toward zero.
- The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

**Example 1:**

**Input:** ["2", "1", "+", "3", "*"]

**Output:** 9

**Explanation:** ((2 + 1) * 3) = 9

**Example 2:**

**Input:** ["4", "13", "5", "/", "+"]

**Output:** 6

**Explanation:** (4 + (13 / 5)) = 6

When the current element is not a number, we will pop out 2 elements from the stack and perform the operation. When the current element is a number, we just append it to the stack.

`class Solution {`

public int evalRPN(String[] tokens) {

Stack<String> st = new Stack<>();

for(int i=0; i<tokens.length; i++){

String tok = tokens[i];

if(tok.equals("+")){

String first = st.pop();

String second = st.pop();

String res = String.valueOf(Integer.parseInt(first) + Integer.parseInt(second));

st.push(res);

} else if (tok.equals("-")){

String first = st.pop();

String second = st.pop();

String res = String.valueOf(Integer.parseInt(second) - Integer.parseInt(first));

st.push(res);

} else if (tok.equals("*")){

String first = st.pop();

String second = st.pop();

String res = String.valueOf(Integer.parseInt(second) * Integer.parseInt(first));

st.push(res);

} else if (tok.equals("/")){

String first = st.pop();

String second = st.pop();

String res = String.valueOf(Integer.parseInt(second) / Integer.parseInt(first));

st.push(res);

} else {

// number

st.add(tok);

}

}

return Integer.parseInt(st.pop());

}

Not the neatest code but it works.

`class Solution {`

public:

unordered_map<string, function<int(int, int)>> opMap {

{"+", [](int a, int b) { return a + b; }},

{"-", [](int a, int b) { return a - b; }},

{"*", [](int a, int b) { return a * b; }},

{"/", [](int a, int b) { return floor(a / b); }},

};

int evalRPN(vector<string>& tokens) {

stack<int> s {};

int a, b;

int res = 0;

for (string& token : tokens) {

if (opMap.find(token) == opMap.end()) {

s.push(stoi(token));

continue;

}

a = s.top(); // read element

s.pop(); // remove element

b = s.top();

s.pop();

s.push(opMap[token](b, a)); // evaluate

}

return s.top();

}

};

## 8) Leet Code 14 Longest Common Prefix

Write a function to find the longest common prefix string among an array of strings.

If there is no common prefix, return an empty string `""`

.

**Example 1:**

**Input: **["flower","flow","flight"]

**Output:** "fl"

**Example 2:**

**Input: **["dog","racecar","car"]

**Output:** ""

**Explanation:** There is no common prefix among the input strings.

`class Solution {`

public String longestCommonPrefix(String[] strs) {

String prefix = strs[0];

for(int i=1; i<strs.length; i++){

String curr = strs[i];

while(!curr.startsWith(prefix) && prefix!=""){

prefix=prefix.substring(0, prefix.length()-1); // remove last char

}

}

return prefix;

}

}

// in c++, to get startsWith, we use the find() method where, str.find(prefix) == 0

- Set prefix to be the first string in the strs array
- As we iterate through the other elements of the string array, we make the prefix smaller and smaller if it does not exist in the first few parts of the string. We remove the last character.

## 9) Leetcode 179 form the largest number

Given a list of non negative integers, arrange them such that they form the largest number.

**Example 1:**

**Input:** [10,2]

**Output:** "210"

**Using comparator:**

It **returns** a positive **value** if obj1 is greater than obj2. Otherwise, a negative **value** is **returned**. By overriding compare( ), you can alter the way that objects are ordered.

**NumComparator will arrange a in front of b => (a,b) if we return a positive value.**- If we want b to be arranged in front of a => (b,a) We need a negative value to be returned. When do we want this arrangement, (b,a)? When (b+a) > (a+b).
**String compareTo: If first string is lexicographically greater than second string, it returns positive number.**- Hence, we want to make sure that we compare (b+a).compareTo(a+b) which corresponds to the code above.
- order2.compareTo( order1); Returns negative when order1 is smaller. Hence, when order1 is smaller, it means a+b < b+a. This means we dont want a to be put in front of b and we can directly return.
- Note that in the comparator, we don’t convert the order1 and order2 into Integers and compare their numerical value. This is because we don’t want to have integer overflow.

`class Solution {`

public:

string largestNumber(vector<int>& nums) {

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

std::sort(nums.begin(), nums.end(), [](int num1, int num2){

string string1 = to_string(num1) + to_string(num2);

string string2 = to_string(num2) + to_string(num1);

return string1 > string2;

// The comparator function should return true if the element a should be placed before the element b in the sorted order, and false otherwise.

});

int first = nums[0];

if(first==0) {

cout << "ll" << endl;

string hi("0");

return hi;

}

cout<<"Pass"<<endl;

string result = "";

for(int n: nums){

result += to_string(n);

}

return result;

}

};

## 10. ZigZag Conversion

The string `"PAYPALISHIRING"`

is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

`P A H N`

A P L S I I G

Y I R

And then read line by line: `"PAHNAPLSIIGYIR"`

Write the code that will take a string and make this conversion given a number of rows:

`string convert(string s, int numRows);`

**Example 1:**

**Input:** s = "PAYPALISHIRING", numRows = 3

**Output:** "PAHNAPLSIIGYIR"

**Example 2:**

Input:s = "PAYPALISHIRING", numRows = 4Output:"PINALSIGYAHRPI"Explanation:P I N

A L S I G

Y A H R

P I

- Create an index that iterate from row 0…numRows, then back to 0 and repeat.

`class Solution {`

public String convert(String s, int numRows) {

if (numRows==1) return s;

LinkedList<Character> [] res = new LinkedList[numRows];

for(int i=0; i<numRows; i++){

res[i] = new LinkedList<Character>();

}

int row=0;

boolean directionGoDown = true;

for(int i=0; i<s.length(); i++){

char c = s.charAt(i);

res[row].add(c);

if (row==numRows-1){

row=row-1;

directionGoDown = false;

} else if (row == 0){

row=row+1;

directionGoDown = true;

} else if (directionGoDown){

row++;

} else if (!directionGoDown){

row--;

}

}

String resultString = "";

for(int i=0; i<numRows; i++){

LinkedList<Character> currRow = res[i];

for(Character c: currRow){

resultString+=c;

}

}

return resultString;

}

}

# Leetcode 281 Zigzag iterator

Given two vectors of integers `v1`

and `v2`

, implement an iterator to return their elements alternately.

Implement the `ZigzagIterator`

class:

`ZigzagIterator(List<int> v1, List<int> v2)`

initializes the object with the two vectors`v1`

and`v2`

.`boolean hasNext()`

returns`true`

if the iterator still has elements, and`false`

otherwise.`int next()`

returns the current element of the iterator and moves the iterator to the next element.

**Example 1:**

`Input: v1 = [1,2], v2 = [3,4,5,6]`

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

Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

**Example 2:**

`Input: v1 = [1], v2 = []`

Output: [1]

**Example 3:**

`Input: v1 = [], v2 = [1]`

Output: [1]

`public class ZigzagIterator {`

private List<List<Integer>> vectors = new ArrayList<>();

private LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();

public ZigzagIterator(List<Integer> v1, List<Integer> v2) {

this.vectors.add(v1);

this.vectors.add(v2);

int index=0;

for(List<Integer> vec: vectors){

if(vec.size()>0){

this.queue.add(new Pair<Integer, Integer> (index, 0));

}

index++;

}

}

public int next() {

Pair<Integer, Integer> pointer = this.queue.removeFirst();

Integer vecIndex = pointer.getKey();

Integer elemIndex = pointer.getValue();

Integer nextElemIndex = elemIndex+1;

if(nextElemIndex < this.vectors.get(vecIndex).size()){

this.queue.addLast(new Pair<>(vecIndex, nextElemIndex));

}

return this.vectors.get(vecIndex).get(elemIndex);

}

public boolean hasNext() {

this.queue.size()>0;

}

}

/**

* Your ZigzagIterator object will be instantiated and called as such:

* ZigzagIterator i = new ZigzagIterator(v1, v2);

* while (i.hasNext()) v[f()] = i.next();

*/

## 11. Leetcode 916 Word Subsets

We are given two arrays `A`

and `B`

of words. Each word is a string of lowercase letters.

Now, say that word `b`

is a subset of word `a`

** **if every letter in `b`

occurs in `a`

, **including multiplicity**. For example, `"wrr"`

is a subset of `"warrior"`

, but is not a subset of `"world"`

.

Now say a word `a`

from `A`

is *universal* if for every `b`

in `B`

, `b`

is a subset of `a`

.

Return a list of all universal words in `A`

. You can return the words in any order.

**Example 1:**

**Input: **A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]

**Output: **["facebook","google","leetcode"]

`class Solution {`

public List<String> wordSubsets(String[] words1, String[] words2) {

int[] count = new int[26];

int[] tmp;

for(String word: words2){

tmp = counter(word);

for(int j=0; j<26; j++){

count[j] = Math.max(count[j], tmp[j]); // why do we need this?? SO that we add on to the count of the previous word in words2

}

}

// At this point, count will contain all the counts of words2

List<String> res = new ArrayList<>();

for(String wordSingle: words1){

tmp = counter(wordSingle);

int i=0;

for(i=0; i<26; ++i){

// every word in words2 has to be found in

// words1.

// Whatever that is in words1 has to be <= words2

if(tmp[i] < count[i]) break;

}

if(i==26) res.add(wordSingle);

}

return res;

}

int[] counter(String word){

int[]count = new int[26];

for(char c: word.toCharArray()){

count[c-'a']++;

}

return count;

}

}

Below is my original attempt, that is wrong…i think i misunderstood the question.

`class Solution {`

public List<String> wordSubsets(String[] words1, String[] words2) {

Map<String, Integer> map2 = new HashMap<>();

for(String s: words2){

int count = map2.getOrDefault(s, 0);

map2.put(s, count+1);

} // I think why this code doesnt work is because if s is made up of

// more than 1 chars, then we don't want it to be in the hashmap as

// for example, "ab". We want to separate them and store "a" and "b"

System.out.println(map2);

List<String> result = new LinkedList<>();

for(String word: words1){

boolean toAdd = true;

for(Map.Entry<String, Integer> entry: map2.entrySet()){

int count = countSubstring(word, entry.getKey());

if (count < entry.getValue()){

toAdd = false;

}

}

if(toAdd){

result.add(word);

}

}

return result;

}

public static int countSubstring(String str, String subStr) {

int count = 0;

int index = 0;

while ((index = str.indexOf(subStr, index)) != -1) {

count++;

index += subStr.length();

}

return count;

}

}

## 12 Leetcode 376 Wriggle Subsequence

A sequence of numbers is called a **wiggle sequence** if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, `[1,7,4,9,2,5]`

is a wiggle sequence because the differences `(6,-3,5,-7,3)`

are alternately positive and negative. In contrast, `[1,4,7,2,5]`

and `[1,7,4,5,5]`

are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

`// wrong and completed attempt `

public int wiggleMaxLength(int[] nums) {

if (nums.length <= 2) return nums.length;

int max = 1;

Info[] dp = new Info[nums.length];

dp[0] = new Info(1, false, true);

if (nums[1] == nums[0]){

dp[1] = new Info(1, false, true);

} else if (nums[1] > nums[0]){

dp[1] = new Info(2, true);

} else {

dp[1] = new Info(2, false);

}

max = Math.max(max, dp[1].length);

for(int i=2; i<nums.length; i++){

int currNum = nums[i];

Info curr = new Info(2, false);

for(int j=i-1; j>=0; j--){

Info prev = dp[j];

int prevNum = nums[j];

if((prev.restart || prev.nextShouldBeNegative) && currNum < prevNum){

curr.length = Math.max(1 + prev.length, curr.length);

curr.nextShouldBeNegative = false;

curr.restart = false;

dp[i] = curr;

} else if ((prev.restart || !prev.nextShouldBeNegative) && currNum > prevNum){

curr.length = Math.max(1 + prev.length, curr.length);

curr.nextShouldBeNegative = true;

curr.restart = false;

dp[i] = curr;

} else {

curr.restart = true;

curr.

}

}

dp[i] = curr;

System.out.print(i);

System.out.print(" ");

System.out.print(dp[i].length);

System.out.println(dp[i].nextShouldBeNegative);

max = Math.max(max, dp[i].length);

}

return max;

}

public static class Info{

private int length;

private boolean nextShouldBeNegative;

private boolean restart;

public Info(int length, boolean nextShouldBeNegative){

this.length = length;

this.nextShouldBeNegative = nextShouldBeNegative;

this.restart = false;

}

public Info(int length, boolean nextShouldBeNegative, boolean restart){

this.length = length;

this.nextShouldBeNegative = nextShouldBeNegative;

this.restart = restart;

}

}

## 13 Leetcode 324 Wiggle Sort II

Given an unsorted array `nums`

, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`

.

**Example 1:**

**Input: **nums = [1, 5, 1, 1, 6, 4]

**Output: **One possible answer is [1, 4, 1, 5, 1, 6].

**Example 2:**

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

**Output:** One possible answer is [2, 3, 1, 3, 1, 2].

**Solution #1**

A pretty simple and straightforward solution is:

- Sort the array (with an auxiliary array)
- Copy the elements to the correct positions

It’s the code:

`class Solution {`

public void wiggleSort(int[] nums) {

int[] val = Arrays.copyOf(nums, nums.length);

Arrays.sort(val);

int idx = val.length - 1;

for(int i = 1;i < nums.length;i += 2) nums[i] = val[idx--];

for(int i = 0;i < nums.length;i += 2) nums[i] = val[idx--];

}

}

Note that we don’t need to calculate all the concrete positions to be copied; we just need to go through the array by odd and even positions till exhausting the array.

The space complexity is O(N), and the time complexity is O(NlogN) + O(N) (sorting + filling) = **O(NlogN)**.

**Solution #2**

To achieve space complexity O(1) and time complexity O(N), a popular approach is:

The idea is based on the fact that if we make sure that all even positioned (at index 0, 2, 4, ..) elements are greater than their adjacent odd elements.

We traverse an array once, visiting all even positions. Then, make sure that the numbers at even positions are greater than its left and right elements. If it is not bigger, then we swap them.

# Leetcode 239: Sliding Window Maximum

You are given an array of integers `nums`

, there is a sliding window of size `k`

which is moving from the very left of the array to the very right. You can only see the `k`

numbers in the window. Each time the sliding window moves right by one position.

Return *the max sliding window*.

**Example 1:**

`Input: nums = [1,3,-1,-3,5,3,6,7], k = 3`

Output: [3,3,5,5,6,7]

Explanation:

Window position Max

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

**Example 2:**

`Input: nums = [1], k = 1`

Output: [1]

` public int[] maxSlidingWindow(int[] nums, int k) {`

List<Integer> output = new ArrayList<>();

Deque<Integer> q = new LinkedList<>();

int l = 0, r = 0;

while(r < nums.length) {

// pop smaller values from q

while(!q.isEmpty() && nums[q.peekLast()] < nums[r]) {

q.pollLast();

}

q.offer(r);

// Remove value in the queue that is outside of the curr window

// range (The one right before)

if (l > q.peek()) {

// q.peek() check head..if the left index is more than the index of the value in queue

q.poll(); // remove head

}

// store the rightmost value in the output.

if ((r + 1) >= k) {

output.add(nums[q.peek()]);

l++;

}

r++;

}

int[] result = new int[nums.length-k+1];

for(int j=0; j<output.size(); j++){

result[j] = output.get(j);

}

return result;

}

We maintain a deque (double-ended queue) to keep track of the maximum value in the current sliding window. We iterate through the input array `nums`

and maintain the deque such that it is a monotonically decreasing queue.

`class Solution {`

public int[] maxSlidingWindow(int[] nums, int k) {

int[] result = new int[nums.length-k+1];

Deque<Integer> q = new LinkedList<>();

int r=0;

for(int i=0; i<nums.length; i++){

while(q.size()>0 && nums[i] > nums[q.peekLast()]){

q.removeLast(); // remove values smaller than nums[i]

}

q.addLast(i);

if(q.peekFirst()<i-k+1){

q.removeFirst(); // remove index out of range

}

if(i>=k-1){

result[r++]=nums[q.peekFirst()];

}

}

return result;

}

}

If we have a window, and we see a value that is greater than values before it, we can ignore all the values before it. Remove them from our window since that value will definitely be the maximum as long as it is within our current window range.

An example to consider:

[8,7,6,9], k =2

`[8], i=0`

[8,7], i=1, result=[8]

[7,6], i=2, result=[8,7]

[9], i=3, result[8,7,9]

**The max value will always be at the head of the queue.**

At each iteration,

Then, we always add current value into the queue.

The queue is monotonically decreasing.

**The algorithm is:**

**1. always pop from head of queue to remove out of range values**

**2. check current value against queue’s items from back to front. We will pop a value from the back of the queue if the value in queue is smaller than the current val. Since we know current val will be the max for current range.**

**3. add current value to queue.**

**4. get max value from the head of the queue. Add to result.**

Note that our queue stores index so that we can check for out of range easily.

The solution given by leetcode is hard to understand, so i wont copy it here.

# 329. Longest Increasing Path in a Matrix

Given an `m x n`

integers `matrix`

, return *the length of the longest increasing path in *`matrix`

.

From each cell, you can either move in four directions: left, right, up, or down. You **may not** move **diagonally** or move **outside the boundary** (i.e., wrap-around is not allowed).

**Example 1:**

`Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]`

Output: 4

Explanation: The longest increasing path is [1, 2, 6, 9].

**Example 2:**

`Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]`

Output: 4

Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

**Example 3:**

`Input: matrix = [[1]]`

Output: 1

`class Solution {`

int[][] cache;

public int longestIncreasingPath(int[][] matrix) {

cache = new int[matrix.length][matrix[0].length];

int longest = 0;

for(int i=0; i<matrix.length; i++){

for(int j=0; j<matrix[0].length; j++){

int len = traverse(matrix, i, j, -1);

longest = Math.max(len, longest);

}

}

return longest;

}

public int traverse(int[][] matrix, int i, int j, int prev){

if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length){

return 0;

}

if(matrix[i][j]<=prev){

return cache[i][j]=0;

}

if(cache[i][j] != 0){

return cache[i][j];

}

int left = traverse(matrix, i, j-1, matrix[i][j]);

int right = traverse(matrix, i, j+1, matrix[i][j]);

int up = traverse(matrix, i-1, j, matrix[i][j]);

int down = traverse(matrix, i+1, j, matrix[i][j]);

return cache[i][j] = Math.max(left, Math.max(right, Math.max(up, down))) + 1;

}

}

# Leetcode 688 Knight probability in chessboard

`class Solution {`

public double knightProbability(int n, int k, int row, int column) {

double[][]dp = new double[n][n];

int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};

int[] dc = new int[]{1, -2, 2, -2, 2, -2, 1, -1};

dp[row][column]=1;

for(int steps=k; steps>0; steps--){

double[][]dp2 = new double[n][n];

for(int rr=0; rr<n; rr++){

for(int cc=0; cc<n; cc++){

for(int step=0; step<8; step++){

int newRow = rr + dr[step];

int newCol = cc + dc[step];

if (0 <= newRow && newRow < n && 0 <= newCol && newCol < n){

dp2[newRow][newCol] += dp[rr][cc] / 8.0;

}

}

}

}

dp = dp2;

}

double ans = 0.0;

for (double[] r: dp) {

for (double x: r) ans += x;

}

return ans;

}

}

i don’t even know what this question is asking…gonna ignore it and hope it doesn’t come up in my interviews.

# Leet code 966 Vowel Spellchecker

Given a `wordlist`

, we want to implement a spellchecker that converts a query word into a correct word.

For a given `query`

word, the spell checker handles two categories of spelling mistakes:

**Capitalization**: If the query matches a word in the wordlist (**case-insensitive**), then the query word is returned with the same case as the case in the wordlist.

- Example:
`wordlist = ["yellow"]`

,`query = "YellOw"`

:`correct = "yellow"`

- Example:
`wordlist = ["Yellow"]`

,`query = "yellow"`

:`correct = "Yellow"`

- Example:
`wordlist = ["yellow"]`

,`query = "yellow"`

:`correct = "yellow"`

**Vowel Errors**: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (**case-insensitive**), then the query word is returned with the same case as the match in the wordlist.

- Example:
`wordlist = ["YellOw"]`

,`query = "yollow"`

:`correct = "YellOw"`

- Example:
`wordlist = ["YellOw"]`

,`query = "yeellow"`

:`correct = ""`

(no match) - Example:
`wordlist = ["YellOw"]`

,`query = "yllw"`

:`correct = ""`

(no match)

In addition, the spell checker operates under the following precedence rules:

- When the query exactly matches a word in the wordlist (
**case-sensitive**), you should return the same word back. - When the query matches a word up to capitalization, you should return the first such match in the wordlist.
- When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
- If the query has no matches in the wordlist, you should return the empty string.

Given some `queries`

, return a list of words `answer`

, where `answer[i]`

is the correct word for `query = queries[i]`

.

Note that all cases are exclusive….Need to be clear of the question.

Why do we use putIfAbsent? Why not use the two code of lines below?

wordSetLowerCase.put(lower, word);

deVowel.put(devowel, word);

In the example above, the bottom 2 are the ones we want (for the two sets).

Ans: If we have 2 similar words, we want to use the one that comes first.

`For C++`

string str = “Hello World”;

// convert to lowercase

std::transform(str.begin(), str.end(), str.begin(), [](unsigned char c){

return std::tolower(c);

});

// replace vowels with ‘#’

std::replace_if(str.begin(), str.end(), [](unsigned char c){

return std::string(“aeiou”).find(std::tolower(c)) != std::string::npos;

}, “#”);

// npos is used to represent char/substring is not found in a string.

## Leet Code 1024 Video Stitching

You are given a series of video clips from a sporting event that lasted `T`

seconds. These video clips can be overlapping with each other and have varied lengths.

Each video clip `clips[i]`

is an interval: it starts at time `clips[i][0]`

and ends at time `clips[i][1]`

. We can cut these clips into segments freely: for example, a clip `[0, 7]`

can be cut into segments `[0, 1] + [1, 3] + [3, 7]`

.

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event (`[0, T]`

). If the task is impossible, return `-1`

.

**Example 1:**

**Input: **clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10

**Output: **3

**Explanation: **

We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.

Then, we can reconstruct the sporting event as follows:

We cut [1,9] into segments [1,2] + [2,8] + [8,9].

Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

**Example 2:**

**Input: **clips = [[0,1],[1,2]], T = 5

**Output: **-1

**Explanation: **

We can't cover [0,5] with only [0,1] and [1,2].

**Example 3:**

**Input: **clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9

**Output: **3

**Explanation: **

We can take clips [0,4], [4,7], and [6,9].

**Example 4:**

**Input: **clips = [[0,4],[2,8]], T = 5

**Output: **2

**Explanation: **

Notice you can have extra video after the event ends.

Note that sorting in Java and C++ is different. In the above, we get ascending order. In C++, the natural order is descending.

Eg, if we have a priority queue, the following will lead to descending order.

`auto compare = [](const MyStruct& a, const MyStruct& b) {`

return a.value - b.value; // if put a in front of b, return positive value. Will be ordered in descending.

};

std::priority_queue<MyStruct, std::vector<MyStruct>, decltype(compare)> pq(compare);

## Leet code 215. Kth Largest Element in an Array

Find the **k**th largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

**Example 1:**

**Input:** [3,2,1,5,6,4] and k = 2

**Output:** 5

**Example 2:**

**Input:** [3,2,3,1,2,4,5,5,6] and k = 4

**Output:** 4

The hard part about this question is that we** have to do it in O(n) time **instead of O(NlogN).

## The idea: Quick Select algorithm

The condition at the WHILE loop has to be while left ≤ right. If we remove equality, then we miss the below case where we only have 1 element …

`class Solution {`

public int findKthLargest(int[] nums, int k) {

return quickSelect(nums, nums.length-k);

}

public int quickSelect(int[] nums, int k){

int low=0;

int right=nums.length-1;

while(low<=right){

// low is the first elem...pivot

int newPivotIndex = low;

for(int i=low+1; i<=right; i++){

if(nums[i]<nums[low]){// compare current val with pivot value...

newPivotIndex++;

swap(nums, newPivotIndex, i);

}

}

swap(nums, newPivotIndex, low);

if(newPivotIndex<k){

low=newPivotIndex+1;

} else if (newPivotIndex>k){

right=newPivotIndex-1;

} else{

return nums[newPivotIndex];

}

}

return -1;

}

public static void swap(int[] nums, int i, int j){

int temp = nums[i];

nums[i]=nums[j];

nums[j]=temp;

}

}

Another Solution is to use Heap.

## Leetcode 973. K Closest Points to Origin

We have a list of `points`

on the plane. Find the `K`

closest points to the origin `(0, 0)`

.

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

**Example 1:**

**Input: **points = [[1,3],[-2,2]], K = 1

**Output: **[[-2,2]]

**Explanation: **

The distance between (1, 3) and the origin is sqrt(10).

The distance between (-2, 2) and the origin is sqrt(8).

Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.

We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

**Example 2:**

**Input: **points = [[3,3],[5,-1],[-2,4]], K = 2

**Output: **[[3,3],[-2,4]]

(The answer [[-2,4],[3,3]] would also be accepted.)

Leet Code Solution:

`class Solution {`

public:

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {

quickSelect(points, 0, points.size() - 1, k);

return vector<vector<int>>(points.begin(), points.begin() + k);

}

void quickSelect(vector<vector<int>>& points, int start, int end, int k) {

if (start >= end) return;

int partitionIndex = partition(points, start, end);

if(partitionIndex==k-1){

return;

} else if (partitionIndex>k-1){

quickSelect(points, start, partitionIndex-1, k);

} else {

quickSelect(points, partitionIndex+1, end, k);

}

}

int partition(vector<vector<int>>& points, int start, int end) {

int pivotIndex = start;

double pivotVal = computeDistance(points[start][0], points[start][1]);

for (int i = start + 1; i <= end; i++) {

if (computeDistance(points[i][0], points[i][1]) < pivotVal) {

swap(points[i], points[++pivotIndex]);

}

}

swap(points[start], points[pivotIndex]);

return pivotIndex;

}

double computeDistance(int x, int y) {

return sqrt(x * x + y * y);

}

};

!!!! NEED TO USE DOUBLE otherwise sqrt will cause precision issues.

## 347. Top K Frequent Elements

Given an integer array `nums`

and an integer `k`

, return *the* `k`

*most frequent elements*. You may return the answer in **any order**.

**Example 1:**

`Input: nums = [1,1,1,2,2,3], k = 2`

Output: [1,2]

**Example 2:**

`Input: nums = [1], k = 1`

Output: [1]

`class Solution {`

HashMap<Integer, Integer> valueToCount; // num to freq

int[] unique; // contains all unique nums

public int[] topKFrequent(int[] nums, int k) {

valueToCount = new HashMap<>();

for(int i=0; i<nums.length; i++){

int count = valueToCount.getOrDefault(nums[i], 0);

valueToCount.put(nums[i], count+1);

}

int n = valueToCount.size();

unique = new int[n];

int i=0;

for(int num: valueToCount.keySet()){

unique[i]=num;

i++;

}

// kth top element is (n-k)th less frequent.

// elements on left are less freq than right

quickSelect(0, n-1, n-k); // do quick select on freq

// Select top k freq elements

return Arrays.copyOfRange(unique, n - k, n);

}

public void quickSelect(int left, int right, int kSmallest){

if(left == right) return;

int pivotIndex = partition(left, right);

if(pivotIndex == kSmallest) return;

else if (pivotIndex > kSmallest){

quickSelect(left, pivotIndex-1, kSmallest);

} else {

quickSelect(pivotIndex+1, right, kSmallest);

}

}

/*

* Here, left and right represent the indices of the leftmost and rightmost elements of the subarray being sorted.

pivotValue represents the value of the pivot element, and pivotIndex represents the index of the last element that is smaller

than the pivot element.

The loop iterates over each element in the subarray, moving smaller elements to the left of pivotIndex. Once the loop is complete,

the pivot element is swapped with the element at pivotIndex, which places it in its final position in the sorted array.

Finally, pivotIndex is returned as the index of the pivot element in the sorted array.

*/

public int partition(int left, int right){

/*

* it generates a random integer between left and right, inclusive. Here, we first compute the length of the subarray

as (right - left + 1). We then multiply this length by a random number between 0 and 1 using Math.random(), which gives

us a random number between 0 and the length of the subarray. Finally, we add left to this random number to get a random

index between left and right

*/

int randomIndex = left + (int)(Math.random() * (right - left + 1));

// 1: swap random index and right

swap(unique, right, randomIndex);

// 2 : now the unique[right] is pivot

int pivotValue = unique[right];

int pivotIndex = left;

for (int i = left; i < right; i++) {

if (valueToCount.get(unique[i]) < valueToCount.get(pivotValue)) {

// move smaller values to the left of pivotIndex

swap(unique, i, pivotIndex++);

}

}

// swap the pivot value with the value at pivotIndex

swap(unique, right, pivotIndex);

return pivotIndex;

}

public void swap(int[] unique, int l, int r) {

int temp = unique[l];

unique[l] = unique[r];

unique[r] = temp;

}

}

- Quick Select: O(n) average case, O(n²) worst case
- Quick Sort: O(n log n) average case, O(n²) worst case

In the code snippets provided earlier, the pivot element for Quick Sort and Quick Select is chosen to be the last element in the subarray being sorted. This is a simple and efficient way to choose a pivot element, but it can lead to worst-case behavior if the input array is already sorted or nearly sorted.

Eg, the partitioning step will always choose the first element as the pivot element, and the loop will move all the elements to the right of the pivot element. This means that the partitioning step will only move the pivot element one position to the right.

`public static void quickSort(int[] arr, int left, int right) {`

if (left < right) {

int pivotIndex = partition(arr, left, right);

quickSort(arr, left, pivotIndex - 1);

quickSort(arr, pivotIndex + 1, right);

}

}

private static int partition(int[] arr, int left, int right) {

int pivot = arr[right];

int i = left;

for (int j = left; j < right; j++) {

if (arr[j] <= pivot) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++;

}

}

int temp = arr[i];

arr[i] = arr[right];

arr[right] = temp;

return i;

}

**quick select and quick sort algo is the same except that quick select will discard half of the array each time according to the pivotIndex value.**

## Leetcode 43 Multiply Strings

Given two non-negative integers `num1`

and `num2`

represented as strings, return the product of `num1`

and `num2`

, also represented as a string.

**Example 1:**

**Input:** num1 = "2", num2 = "3"

**Output:** "6"

**Example 2:**

**Input:** num1 = "123", num2 = "456"

**Output:** "56088"

**Note:**

- The length of both
`num1`

and`num2`

is < 110. - Both
`num1`

and`num2`

contain only digits`0-9`

. - Both
`num1`

and`num2`

do not contain any leading zero, except the number 0 itself. - You
**must not use any built-in BigInteger library**or**convert the inputs to integer**directly.ma

## Leet code 780 Reaching Points

A move consists of taking a point `(x, y)`

and transforming it to either `(x, x+y)`

or `(x+y, y)`

.

Given a starting point `(sx, sy)`

and a target point `(tx, ty)`

, return `True`

if and only if a sequence of moves exists to transform the point `(sx, sy)`

to `(tx, ty)`

. Otherwise, return `False`

.

Examples:Input:sx = 1, sy = 1, tx = 3, ty = 5Output:TrueExplanation:

One series of moves that transforms the starting point to the target is:

(1, 1) -> (1, 2)

(1, 2) -> (3, 2)

(3, 2) -> (3, 5)Input:sx = 1, sy = 1, tx = 2, ty = 2Output:FalseInput:sx = 1, sy = 1, tx = 1, ty = 1Output:True

We work backwards to find the answer, trying to transform the target point to the starting point via applying the parent operation `(x, y) -> (x-y, y) or (x, y-x)`

depending on which one doesn't have negative coordinates.

First, we keep reducing tx and ty to values until one of the tx==sx or ty==sy. At this point, we know we are at a point located either horizontal from the source or vertical from the source.

So if it is located horizontally away from source, then ty==sy will be true. So we keep reducing tx value. We see if we can move from tx to sx with ty steps.

## Leetcode 300 Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

**Example:**

**Input:** [10,9,2,5,3,7,101,18]

**Output: **4

**Explanation: **The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

`class Solution {`

public int lengthOfLIS(int[] nums) {

int[] dp = new int[nums.length]; // dp[i]: max length if we must include number at ith position

Arrays.fill(dp, 1); // need to initialise to 1 since this is the min max length if we include the number at i

int max = 1;

for(int n=1; n<nums.length; n++){

for(int j=n-1 ; j>=0; j--){

if(nums[n]>nums[j]){

dp[n]=Math.max(dp[n], dp[j]+1);

}

}

max = Math.max(max, dp[n]);

}

return max;

}

}

We need to have a variable max instead of returning dp[last index] because the last element might not be included in the longest sequence.

## Leet code 775. Global and Local Inversions

We have some permutation `A`

of `[0, 1, ..., N - 1]`

, where `N`

is the length of `A`

.

The number of (global) inversions is the number of `i < j`

with `0 <= i < j < N`

and `A[i] > A[j]`

.

The number of local inversions is the number of `i`

with `0 <= i < N`

and `A[i] > A[i+1]`

.

Return `true`

if and only if the number of global inversions is equal to the number of local inversions.

- NOTE THAT: The values in the array are 0,1…n

**Example 1:**

**Input:** A = [1,0,2]

**Output:** true

**Explanation:** There is 1 global inversion, and 1 local inversion.

**Example 2:**

**Input:** A = [1,2,0]

**Output:** false

**Explanation:** There are 2 global inversions, and 1 local inversion.

## 1249. Minimum Remove to Make Valid Parentheses

Given a string s of `'('`

, `')'`

and lowercase English characters.

Your task is to **remove the minimum number of parentheses** ( `'('`

or `')'`

, in any positions ) so that the resulting *parentheses string* is valid and return **any** valid string.

Formally, a *parentheses string* is valid if and only if:

- It is the empty string, contains only lowercase characters, or
- It can be written as
`AB`

(`A`

concatenated with`B`

), where`A`

and`B`

are valid strings, or - It can be written as
`(A)`

, where`A`

is a valid string.

**Example 1:**

**Input:** s = "lee(t(c)o)de)"

**Output:** "lee(t(c)o)de"

**Explanation:** "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

**Example 2:**

**Input:** s = "a)b(c)d"

**Output:** "ab(c)d"

**Example 3:**

**Input:** s = "))(("

**Output:** ""

**Explanation:** An empty string is also valid.

**Example 4:**

**Input:** s = "(a(b(c)d)"

**Output:** "a(b(c)d)"

- Use a stack to track the indices of the open brackets.
- Whenever you see a closing bracket, pop one out of the stack. If the stack is empty, it means we are dealing with an extra closing bracket. However, we do not immediately remove it. Instead, we do a lazy deletion by substituting it with a symbol #. This is because, later on, when we want to remove the open brackets, the indices is based on the original string. Hence, we want these indices to remain valid.
- At the end of going through all characters, if there are excess open brackets in the stack, we will then need to remove them.
- At the last part, we remove the closing brackets that were lazily removed previously by doing a replaceAll(“#”, “”).
- Note that the commented lines are the same as line 37. However, it is less efficient that line 37 as it does not pass the last test case on leet code.

`// Another attempt...that is correct.`

class Solution {

public String minRemoveToMakeValid(String s) {

String result = "";

Stack<Integer> open = new Stack<>();

for(int i=0; i<s.length(); i++){

if(s.charAt(i) == '('){

open.push(i);

result += "(";

} else if (s.charAt(i) == ')'){

if(open.size()>0){

result+=")";

open.pop();

} else{

result+="&"; // we don't immediately remove ) from result

// even though we will remove it ultimately..this is to make sure that the index

// of open is valid for all (

}

} else {

result += s.substring(i, i+1);

}

}

// Remove all the open bracket

while(open.size()>0){

int pos = open.pop();

if((pos+1)<=result.length()-1){

result=result.substring(0, pos) + "#"+result.substring(pos+1);

} else{

result=result.substring(0, pos) + "#";

}

}

return result.replaceAll("#", "").replaceAll("&", "");

}

}

`// better solution`

class Solution {

public String minRemoveToMakeValid(String s) {

int count=0;

char[] stringChar = s.toCharArray();

for(int i=0; i<stringChar.length; i++){

if(stringChar[i] == '('){

count++;

} else if (stringChar[i] == ')'){

if(count>0){

count--;

} else {

stringChar[i]='#';

}

}

}

for(int i=stringChar.length-1; i>=0; i--){

if(count==0){

break;

}

if(stringChar[i] == '('){

stringChar[i]='#'; // reason why we don't set as '' is because

// empty char literal is not allowed

count--;

}

}

return new String(stringChar).replaceAll("#", "");

}

}

## 301. Remove Invalid Parentheses **

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

**Note:** The input string may contain letters other than the parentheses `(`

and `)`

.

**Example 1:**

**Input:** "()())()"

**Output:** ["()()()", "(())()"]

**Example 2:**

**Input:** "(a)())()"

**Output:** ["(a)()()", "(a())()"]

**Example 3:**

**Input:** ")("

**Output: **[""]

The idea is to make use of recursion to remove brackets from the string. **As long as the current string is not valid, we try to remove one character at different positions from the string **(For loop in line 35–39).

Then, once we have a valid string, we add to results, provided that we checked it is the minimum.

Line 29 might not be needed actually.

The **seenBefore **Hash Set is to help in the time complexity where we store all those strings arrangements that we have seen before.** This helps make sure we do not repeat recursion calls on the same strings.**

`class Solution {`

HashSet<String> seenBefore;

List<String> result;

int maxLen;

public List<String> removeInvalidParentheses(String s) {

seenBefore = new HashSet<>();

result = new LinkedList<>();

maxLen=0;

remove(s);

return result;

}

public void remove(String s){

if(seenBefore.contains(s)) return;

seenBefore.add(s);

if(isValid(s)){

if(s.length()>maxLen){

maxLen=s.length();

result = new LinkedList<>();

result.add(s);

} else if (s.length() == maxLen){

result.add(s);

}

return;

}

for(int i=0; i<s.length(); i++){

String removedBrack = s.substring(0, i)+s.substring(i+1);

remove(removedBrack);

}

}

public boolean isValid(String s){

int count=0;

for(int i=0; i<s.length(); i++){

if(s.charAt(i) == '('){

count++;

} else if(s.charAt(i) == ')'){

if(count>0){

count--;

} else {

return false;

}

}

}

return count==0;

}

}

## 921. Minimum Add to Make Parentheses Valid **

Given a string `S`

of `'('`

and `')'`

parentheses, we add the minimum number of parentheses ( `'('`

or `')'`

, and in any positions ) so that the resulting parentheses string is valid.

Formally, a parentheses string is valid if and only if:

- It is the empty string, or
- It can be written as
`AB`

(`A`

concatenated with`B`

), where`A`

and`B`

are valid strings, or - It can be written as
`(A)`

, where`A`

is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.

**Example 1:**

**Input: **"())"

**Output: **1

**Example 2:**

**Input: **"((("

**Output: **3

**Example 3:**

**Input: **"()"

**Output: **0

**Example 4:**

**Input: **"()))(("

**Output: **4

Line 10: Found a match

Line 11: If the program enters here, it means there is not enough openBrack to match the current close bracket. Hence, need to add one more open ‘(’ bracket.

Line 17: toAddCloseBrack contains the number of unmatched ‘(’ brackets. Hence, this variable tells us the number of close ‘)’ brackets to add.

## 32. Longest Valid Parentheses

*Pretty challenging*

Given a string containing just the characters `'('`

and `')'`

, find the length of the longest valid (well-formed) parentheses substring.

**Example 1:**

**Input:** s = "(()"

**Output:** 2

**Explanation:** The longest valid parentheses substring is "()".

**Example 2:**

**Input:** s = ")()())"

**Output:** 4

**Explanation:** The longest valid parentheses substring is "()()".

**Example 3:**

**Input:** s = ""

**Output:** 0

**Leet Code Solution**:

The ith element of dp represents the length of the longest valid substring ending at ith index.

Now, it’s obvious that the valid substrings must end with ‘)’. This further leads to the conclusion that the substrings ending with ‘(’ will always contain ‘0’ at their corresponding dp indices. Thus, **we update the dp array only when ‘)’ is encountered.**

**i-dp[i-1]** **gives us the starting position of the previous valid string**. We do a -1 to i-dp[i-1] to get the character before it.

- If the character at i-1 is a ‘)’, then we check where is the starting index of the valid substring that ends with i-1? This is given by i-dp[i-1].
- Then, we want to know if there is a ‘( in front of this valid substring. So we check i-dp[i-1]-1 and check if it is == ‘(’.
- If yes, then we need to check the value of dp at the position i-dp[i-1]-2 (olive bracket). If the value dp[i-dp[i-1–2] was previously ≥ 2, then we can add this value (olive)+ 2 (pink and lime green current matching brackets) + most recent valid substring (blue brackets) given by dp[i-1].

Leetcode solution

`public class Solution {`

public int longestValidParentheses(String s) {

int maxans = 0;

Stack<Integer> stack = new Stack<>(); // either the previous invalid point

// or the previous (

stack.push(-1);

for (int i = 0; i < s.length(); i++) {

if (s.charAt(i) == '(') {

stack.push(i); // This will be popped later when we see )

} else {

stack.pop(); // remove the index of previous (, so we can compute len

if (stack.empty()) {

stack.push(i); // why? to mark i as the most recent invalid. So later,

// when we compute length, it will start from i.

} else {

maxans = Math.max(maxans, i - stack.peek());

}

}

}

return maxans;

}

}

## 20. Valid Parentheses

Given a string `s`

containing just the characters `'('`

, `')'`

, `'{'`

, `'}'`

, `'['`

and `']'`

, determine if the input string is valid.

An input string is valid if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.

**Example 1:**

`Input: s = "()"`

Output: true

**Example 2:**

`Input: s = "()[]{}"`

Output: true

**Example 3:**

`Input: s = "(]"`

Output: false

`class Solution {`

public boolean isValid(String s) {

Stack<Character> stack = new Stack<>();

for(int i=0; i<s.length(); i++){

char c = s.charAt(i);

if(c=='(' || c=='{' || c == '['){

stack.push(c);

} else {

if(stack.size()<=0) return false;

char exist = stack.pop();

if((exist=='(' && c !=')') || (exist=='{' && c !='}')|| (exist == '[' && c != ']')){

return false;

}

}

}

return stack.size()==0;

}

}

## Basic Calculator I

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open `(`

and closing parentheses `)`

, the plus `+`

or minus sign `-`

, **non-negative** integers and empty spaces .

**Example 1:**

**Input:** "1 + 1"

**Output:** 2

**Example 2:**

**Input:** " 2-1 + 2 "

**Output:** 3

**Example 3:**

**Input:** "(1+(4+5+2)-3)+(6+8)"

**Output:** 23

This question was quite hard…referred to leetcode solution.

Leet code solution: https://leetcode.com/problems/basic-calculator/discuss/62361/Iterative-Java-solution-with-stack

Simple iterative solution by identifying characters one by one. One important thing is that the input is valid, which means the parentheses are always paired and in order.

Only 5 possible input we need to pay attention:

- digit: it should be one digit from the current number
- ‘+’: number is over, we can add the previous number and start a new number
- ‘-’: same as above
- ‘(‘: push the previous result and the sign into the stack, set result to 0, just calculate the new result within the parenthesis.
- ‘)’: pop out the top two numbers from stack, first one is the sign before this pair of parenthesis, second is the temporary result before this pair of parenthesis. We add them together.

Finally if there is only one number, from the above solution, we haven’t add the number to the result, so we do a check see if the number is zero.

`class Solution {`

public int calculate(String s) {

Stack<Integer> stack = new Stack<Integer>();

int operand = 0;

int result = 0; // For the on-going result

int sign = 1; // 1 means positive, -1 means negative

for (int i = 0; i < s.length(); i++) {

char ch = s.charAt(i);

if (Character.isDigit(ch)) {

// Forming operand, since it could be more than one digit

operand = 10 * operand + (int) (ch - '0');

} else if (ch == '+') {

// Evaluate the expression to the left,

// with result, sign, operand

result += sign * operand;

// Save the recently encountered '+' sign

sign = 1;

// Reset operand

operand = 0;

} else if (ch == '-') {

result += sign * operand;

sign = -1;

operand = 0;

} else if (ch == '(') {

// Push the result and sign on to the stack, for later

// We push the result first, then sign

stack.push(result);

stack.push(sign);

// Reset operand and result, as if new evaluation begins for the new sub-expression

sign = 1;

result = 0;

} else if (ch == ')') {

// Evaluate the expression to the left

// with result, sign and operand

result += sign * operand;

// ')' marks end of expression within a set of parenthesis

// Its result is multiplied with sign on top of stack

// as stack.pop() is the sign before the parenthesis

result *= stack.pop();

// Then add to the next operand on the top.

// as stack.pop() is the result calculated before this parenthesis

// (operand on stack) + (sign on stack * (result from parenthesis))

result += stack.pop();

// Reset the operand

operand = 0;

}

}

return result + (sign * operand);

}

}

## Basic Calculator II (Medium)

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only **non-negative** integers, `+`

, `-`

, `*`

, `/`

operators and empty spaces . The integer division should truncate toward zero.

**Example 1:**

**Input: **"3+2*2"

**Output:** 7

**Example 2:**

**Input:** " 3/2 "

**Output:** 1

**Example 3:**

**Input:** " 3+5 / 2 "

**Output:** 5

The solution given by leetcode is good. (refer to it for explanation). The hard part about this is figuring how to do * and / before + and -.

We know that there could be 4 types of operations — addition `(+)`

, subtraction `(-)`

, multiplication `(*)`

and division `(/)`

. Without parenthesis, we know that, multiplication `(*)`

and `(\)`

operations would always have higher precedence than addition `(+)`

and subtraction `(-)`

based on operator precedence rules.

If we look at the above examples, we can make the following observations

- If the current operation is addition
`(+)`

or subtraction`(-)`

, then the expression is evaluated based on the precedence of the**next operation**.

In example 1, `4+3`

is evaluated later because the next operation is multiplication `(3*5)`

which has higher precedence. But, in example 2, `4+3`

is evaluated first because the next operation is subtraction `(3-5)`

which has equal precedence.

- If the current operator is multiplication
`(*)`

or division`(/)`

, then the expression is evaluated irrespective of the next operation. This is because in the given set of operations`(+,-,*,/)`

, the`*`

and`/`

operations have the highest precedence and therefore must be evaluated first.

……..refer to leetcode solutions……….

`class Solution {`

public int calculate(String s) {

Stack<Integer> stack = new Stack<>();

int prevNum = 0;

char prevSign = '+';

for(int i=0; i<s.length(); i++){

char current = s.charAt(i);

if(Character.isDigit(current)){

prevNum = (prevNum * 10) + (current - '0');

}

if ((!Character.isDigit(current) && !Character.isWhitespace(current)) || i==s.length()-1){

if (prevSign == '+'){

// A + B

// stack is empty

// prevSign = + (The one set by default)

// prevNum = A

// Now at +

stack.push(prevNum);

} else if (prevSign == '-'){

stack.push(-1 * prevNum);

} else if (prevSign == '*'){

// we are already at the next char

// eg, A * B + C

// Currently, we are at +

// A is in the stack, * is prevSign and B is prevNum

stack.push(stack.pop() * prevNum);

} else if (prevSign == '/'){

stack.push(stack.pop() / prevNum);

}

prevSign = current;

prevNum = 0;

}

}

int result = 0;

while(!stack.isEmpty()){

result += stack.pop();

}

return result;

}

}

// Idea: When you see a number, just add it to prevNum

// When you see operator like + or -, push the prevNum value to stack

// When you see * or /, start to evaluate the values...

// The reason why we check for prevSign is because for * and /, we can only start to

// evaluate when we finish looking at x * y

When we encounter a new operator, we will then go on to evaluate the previous operator seen before (stored in the variable `operation`

). According to the sign of the previous operator, it will evaluate the value stored in `previousNum`

which is the number that comes after the previous operator.

Eg, 1+2

- Set
`previousNum`

to 1 - See that current char is + then we see that previous operator is +. Hence, push 1 to stack. Set
`operation`

to + and`previousNum`

to 0. - set
`previousNum`

to 2. See that previous char is +. Push 2 into stack.

When we exit from the for loop, we will then proceed to add up all the numbers in the stack.

## Basic Calculator III

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, `'+'`

, `'-'`

, `'*'`

, `'/'`

operators, and open `'('`

and closing parentheses `')'`

. The integer division should **truncate toward zero**.

You may assume that the given expression is always valid. All intermediate results will be in the range of `[-231, 231 - 1]`

.

**Note:** You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as `eval()`

.

**Example 1:**

`Input: s = "1+1"`

Output: 2

**Example 2:**

`Input: s = "6-4/2"`

Output: 4

**Example 3:**

`Input: s = "2*(5+5*2)/3+(6/2+8)"`

Output: 21

`// First attempt...incorrect`

class Solution {

public int calculate(String s) {

int prevNum = 0;

char prevSign = '+';

Stack<Integer> stack = new Stack<>();

int i=0;

while(i<s.length()){

char curr = s.charAt(i);

if(Character.isDigit(curr)){

prevNum = ( prevNum * 10 ) + (curr - '0');

} else if (curr == '('){

// do recursion

int start = i;

int end = i;

char c = curr;

int countOfOpen = 1;

while(c != ')' && countOfOpen >= 1){

c = s.charAt(end);

if (c == '('){

countOfOpen ++;

}

if (c ==')'){

countOfOpen--;

}

end++;

}

String str = s.substring(start+1, end);

int value = calculate(str);

prevNum = value;

i = end;

continue;

}

if (!Character.isDigit(curr) || i == s.length()-1){

if (prevSign == '+'){

stack.push(prevNum);

} else if (prevSign == '-'){

stack.push(-1 * prevNum);

} else if (prevSign == '*'){

stack.push(stack.pop() * prevNum);

} else if (prevSign == '/'){

stack.push(stack.pop() / prevNum);

}

prevSign = curr;

prevNum = 0;

}

i++;

}

int result = prevNum;

while(!stack.isEmpty()){

result += stack.pop();

}

return result;

}

}

`// Second attempt... correct`

class Solution {

public int calculate(String s) {

int prevNum = 0;

char prevSign = '+';

Stack<Integer> stack = new Stack<>();

int i=0;

while(i<s.length()){

char curr = s.charAt(i);

if(Character.isDigit(curr)){

prevNum = ( prevNum * 10 ) + (curr - '0');

} else if (curr == '('){

// do recursion

int start = i;

int end = i+1;

char c = curr;

int countOfOpen = 1;

// Trying to find the section between the two outermost brackets

while(end < s.length()){

c = s.charAt(end);

if (c == '('){

countOfOpen ++;

}

if (c ==')'){

countOfOpen--;

}

if (countOfOpen == 0) break; // This check needs to be here instead of while condition so that end don't get incremented unnecessarily

end++;

}

String str = s.substring(start+1, end); // exclude the brackets at the both ends

int value = calculate(str);

prevNum = value; // treat whatever value inside the brackets to be a number value.

i = end;

continue; // move to the next index

}

if (!Character.isDigit(curr) || i == s.length()-1){

if (prevSign == '+'){

stack.push(prevNum);

} else if (prevSign == '-'){

stack.push(-1 * prevNum);

} else if (prevSign == '*'){

stack.push(stack.pop() * prevNum);

} else if (prevSign == '/'){

stack.push(stack.pop() / prevNum);

}

prevSign = curr;

prevNum = 0;

}

i++;

}

int result = prevNum;

while(!stack.isEmpty()){

result += stack.pop();

}

return result;

}

}

This is similar to the previous basic calculator II except that we pass the string in the bracket to a recursion function…kind of outsourcing…

Should memorise how basic calculator II works.

## Basic Calculator IV

Given an expression such as `expression = "e + 8 - a + 5"`

and an evaluation map such as `{"e": 1}`

(given in terms of `evalvars = ["e"]`

and `evalints = [1]`

), return a list of tokens representing the simplified expression, such as `["-1*a","14"]`

- An expression alternates chunks and symbols, with a space separating each chunk and symbol.
- A chunk is either an expression in parentheses, a variable, or a non-negative integer.
- A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like
`"2x"`

or`"-x"`

.

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.

- For example,
`expression = "1 + 2 * 3"`

has an answer of`["7"]`

.

The format of the output is as follows:

- For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically.
- For example, we would never write a term like
`"b*a*c"`

, only`"a*b*c"`

. - Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
- For example,
`"a*a*b*c"`

has degree`4`

. - The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed.
- An example of a well-formatted answer is
`["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"]`

. - Terms (including constant terms) with coefficient
`0`

are not included. - For example, an expression of
`"0"`

has an output of`[]`

.

**Note:** You may assume that the given expression is always valid. All intermediate results will be in the range of `[-231, 231 - 1]`

.

**Example 1:**

`Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]`

Output: ["-1*a","14"]

**Example 2:**

`Input: expression = "e - 8 + temperature - pressure", evalvars = ["e", "temperature"], evalints = [1, 12]`

Output: ["-1*pressure","5"]

**Example 3:**

`Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []`

Output: ["1*e*e","-64"]

I didn’t solve this problem because i think it won’t be tested in a real interview…also was lazy…below is a solution copied from someone else..will look at this one day.

`class Solution:`

def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:

evalMap = {}

for e, v in zip(evalvars, evalints):

evalMap[e] = v

def sum_map(st_map):

res = Counter()

for num_map in st_map:

for k, v in num_map.items():

res[k] += v

return res

def multiply(num1, num2):

res = {}

for k1 in num1.keys():

for k2 in num2.keys():

if num1[k1] == 0 or num2[k2] == 0:

continue

mul_key = []

if k1: mul_key += k1.split("*")

if k2: mul_key += k2.split("*")

mul_key = sorted(mul_key)

key = "*".join(mul_key)

res[key] = res.get(key, 0) + num1[k1] * num2[k2]

return res

## Add space to better separate ().

expression = expression.replace("(", "( ")

expression = expression.replace(")", " )")

s = deque(expression.split(" "))

def dfs():

## use empty "" to denote pure number.

st = []

# last_num = {"": 0}

num = {"": 0}

sign = "+"

while len(s) > 0:

char = s.popleft()

if char.isdigit() or char in evalMap:

if char in evalMap:

number = evalMap[char]

else:

number = int(char)

num = {"": number}

elif char.isalpha():

num = {char: 1}

if char == "(":

num = dfs()

if len(s) == 0 or char in "+-*()":

if sign == "+":

st.append(num)

if sign == "-":

for k, v in num.items():

num[k] = -v

st.append(num)

if sign == "*":

st[-1] = multiply(st[-1], num)

sign = char

if char == ")":

break

return sum_map(st)

resMap = dfs()

# Gather final results.

res, f_num = [], []

keys = list(resMap.keys())

keys = sorted(keys, key=lambda x: (-len(x.split('*')), x.split('*')))

for k in keys:

val = resMap[k]

if val == 0:

continue

if k == "":

f_num = [str(val)]

else:

res.append(str(val) + "*" + k)

return res + f_num

## Leetcode 616 Add Bold Tags in a String (Leetcode premium qns)

You are given a string `s`

and an array of strings `words`

.

You should add a closed pair of bold tag `<b>`

and `</b>`

to wrap the substrings in `s`

that exist in `words`

.

- If two such substrings overlap, you should wrap them together with only one pair of closed bold-tag.
- If two substrings wrapped by bold tags are consecutive, you should combine them.

Return `s`

*after adding the bold tags*.

**Example 1:**

`Input: s = "abcxyz123", words = ["abc","123"]`

Output: "<b>abc</b>xyz<b>123</b>"

Explanation: The two strings of words are substrings of s as following: "abcxyz123".

We add <b> before each substring and </b> after each substring.

**Example 2:**

`Input: s = "aaabbb", words = ["aa","b"]`

Output: "<b>aaabbb</b>"

Explanation:

"aa" appears as a substring two times: "aaabbb" and "aaabbb".

"b" appears as a substring three times: "aaabbb", "aaabbb", and "aaabbb".

We add <b> before each substring and </b> after each substring: "<b>a<b>a</b>a</b><b>b</b><b>b</b><b>b</b>".

Since the first two <b>'s overlap, we merge them: "<b>aaa</b><b>b</b><b>b</b><b>b</b>".

Since now the four <b>'s are consecuutive, we merge them: "<b>aaabbb</b>".

- The given dict won’t contain duplicates, and its length won’t exceed 100.
- All the strings in input have length in range [1, 1000].

`class Solution {`

public String addBoldTag(String s, String[] words) {

// iterate through each word in words

// For each word, create a window of the word length

// check if word exist in s..if yes, mark the indexes...

int[] result = new int[s.length()];

for(String w: words){

int windowSize = w.length();

int start=0;

while(start<=s.length()-windowSize){

if(s.substring(start, start+windowSize).equals(w)){

for(int i=start; i<start+windowSize; i++){

result[i] = 1;

}

}

start++;

}

}

String resultString = "";

int r=0;

while(r < result.length){

if(result[r] == 1){

resultString += "<b>" + s.substring(r, r+1);

r++;

while(r < result.length && result[r] == 1){

resultString += s.substring(r, r+1);

r++;

}

resultString += "</b>";

} else{

resultString += s.substring(r, r+1);

r++;

}

}

return resultString;

}

}

This solution is pretty easy to understand once you read it. Loop through all the words in the dictionary, then create a window size of that word you are currently looping at.

Attempt to find matches in the original string. When a match is found, mark each individual character in the bold array as true. True means the character is to be bold. False means no.

## 12. Leetcode 139 Word Break

Given a **non-empty** string *s* and a dictionary *wordDict* containing a list of **non-empty** words, determine if *s* can be segmented into a space-separated sequence of one or more dictionary words.

**Note:**

- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.

`class Solution {`

HashMap<String, Boolean> dp;

public boolean wordBreak(String s, List<String> wordDict) {

dp = new HashMap<>();

return recurse(s, wordDict);

}

public boolean recurse(String s, List<String> wordDict){

if(dp.containsKey(s)) return dp.get(s);

if(s.length() == 0){

dp.put(s, true);

return true;

}

if(s.length()<0){

return false;

}

for(String w: wordDict){

if(s.startsWith(w)){

if(recurse(s.substring(w.length()), wordDict)){

dp.put(s, true);

return true;

}

}

}

dp.put(s, false);

return false;

}

}

# 140. Word Break II

Given a string `s`

and a dictionary of strings `wordDict`

, add spaces in `s`

to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in **any order**.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**Example 1:**

`Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]`

Output: ["cats and dog","cat sand dog"]

**Example 2:**

`Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]`

Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

Explanation: Note that you are allowed to reuse a dictionary word.

**Example 3:**

`Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]`

Output: []

`class Solution {`

public:

unordered_map<string, vector<string>> dp;

vector<string> wordBreak(string s, vector<string>& wordDict) {

return recurse(s, wordDict);

}

vector<string> recurse(string s, vector<string>& wordDict) {

if (dp.count(s) > 0)

return dp[s];

if (s.length() == 0)

return {""};

vector<string> result;

for (string word : wordDict) {

if (s.substr(0, word.length()) == word) {

vector<string> subResult = recurse(s.substr(word.length()), wordDict);

for (string sub : subResult) {

if (sub == "")

result.push_back(word);

else

result.push_back(word + " " + sub);

}

}

}

dp[s] = result;

return result;

}

};

Time complexity: O(n*m) where n is the length of the input and m is the size of wordDict.

In the `recurse`

function, for each substring of `s`

, it iterates over all words in the word dictionary to check if the substring starts with any of those words. This iteration takes O(M) time. If the substring matches a word, the function recursively calls itself on the remaining substring. In the worst case, where the substring matches all words in the word dictionary, the function will make recursive calls for each word, resulting in O(N) recursive calls.

The following questions below makes use of Prefix Sum and Hash Map. Good to be able to spot what type of questions needs this.

## Leet Code 974. Subarray Sums Divisible by K

Given an array `A`

of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by `K`

.

**Example 1:**

**Input: **A = [4,5,0,-2,-3,1], K = 5

**Output: **7

**Explanation: **There are 7 subarrays with a sum divisible by K = 5:

[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

https://www.youtube.com/watch?v=u9m-hnlcydk

When we have X%k=2 and Y%k=2, we get (X-Y)%k = 0.

The idea behind this solution is to calculate the cumulative sum of the items in the given array. For eg, at index i we have the sum of the numbers from position 0,1..i. Then for each index, we store the value of cumulative sum % K.

If we have C counts with remainder 2, then total number of subarrays with remainder 0 derived from the subtraction of the cumulative sums with remainder 2 can be visualised as a **C Choose 2 **problem.

We choose any two points and take their difference to give a remainder of 0. (see image above). The value of the map represents the number of subarrays with their remainder being the key value. we simply choose any 2 arrays within it and we will find a subarray that gives remainder 0. Thus, the problem is a C Choose 2 problem.

The special case is if we have C counts with remainder 0, where the total number of subarrays with remainder 0 will be **C + C Choose 2**. C -> The number of subarrays with already existing remainder 0. The C Choose 2 would be the combination of any 2 subarrays.

Hence, in the code above, we store **count (key) and their associated remainder** **(value)** in **a hashmap**. Formula of C Choose 2 is given to be **C*(C-1)/2**.

## 1010. Pairs of Songs With Total Durations Divisible by 60

You are given a list of songs where the `ith`

song has a duration of `time[i]`

seconds.

Return *the number of pairs of songs for which their total duration in seconds is divisible by* `60`

. Formally, we want the number of indices `i`

, `j`

such that `i < j`

with `(time[i] + time[j]) % 60 == 0`

.

**Example 1:**

`Input: time = [30,20,150,100,40]`

Output: 3

Explanation: Three pairs have a total duration divisible by 60:

(time[0] = 30, time[2] = 150): total duration 180

(time[1] = 20, time[3] = 100): total duration 120

(time[1] = 20, time[4] = 40): total duration 60

**Example 2:**

`Input: time = [60,60,60]`

Output: 3

Explanation: All three pairs have a total duration of 120, which is divisible by 60.

**Constraints:**

`1 <= time.length <= 6 * 104`

`1 <= time[i] <= 500`

`class Solution {`

public int numPairsDivisibleBy60(int[] time) {

int count = 0;

int sum = time[0];

Map<Integer, Integer> map = new HashMap<>(); // remainder to count of vals in time with this remainder

map.put(sum%60, 1);

for(int t=1; t<time.length; t++){

int remainder = time[t]%60;

int other = Math.abs(60-remainder);

// if a value does not have remainder

// 0 when divided by 60, then we need to add it to another number with the

// "opposite" remainder(60-re) so that their sum gives remainder of 0

count+=map.getOrDefault(other, 0);

if(remainder == 0){

count+=map.getOrDefault(remainder, 0);

}

int currCount = map.getOrDefault(remainder, 0);

map.put(remainder, currCount+1);

}

return count;

}

}

## LeetCode 560. Subarray Sum Equals K

Given an array of integers `nums`

and an integer `k`

, return *the total number of continuous subarrays whose sum equals to *

.*k*

**Example 1:**

**Input:** nums = [1,1,1], k = 2

**Output:** 2

**Example 2:**

**Input:** nums = [1,2,3], k = 3

**Output:** 2

## Leet Code 1658. Minimum Operations to Reduce X to Zero

You are given an integer array `nums`

and an integer `x`

. In one operation, you can either remove the leftmost or the rightmost element from the array `nums`

and subtract its value from `x`

. Note that this **modifies** the array for future operations.

Return *the **minimum number** of operations to reduce *`x`

*to **exactly*`0`

*if it's possible, otherwise, return *`-1`

.

**Example 1:**

**Input:** nums = [1,1,4,2,3], x = 5

**Output:** 2

**Explanation:** The optimal solution is to remove the last two elements to reduce x to zero.

**Example 2:**

**Input:** nums = [5,6,7,8,9], x = 4

**Output:** -1

**Example 3:**

**Input:** nums = [3,2,20,1,1,3], x = 10

**Output:** 5

**Explanation:** The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

This question is quite similar to the one above involving the use of prefix sum.

- Very important to identify this problem to be like the problem involving prefix sum and map.

## Leet Code 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers `arr`

and an integer `target`

.

You have to find **two non-overlapping sub-arrays** of `arr`

each with sum equal `target`

. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is **minimum**.

Return *the minimum sum of the lengths* of the two required sub-arrays, or return ** -1** if you cannot find such two sub-arrays.

**Example 1:**

**Input:** arr = [3,2,2,4,3], target = 3

**Output:** 2

**Explanation:** Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

**Example 2:**

**Input:** arr = [7,3,4,7], target = 7

**Output:** 2

**Explanation:** Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

**Example 3:**

**Input:** arr = [4,3,2,6,2,3,4], target = 6

**Output:** -1

**Explanation:** We have only one sub-array of sum = 6.

**Example 4:**

**Input:** arr = [5,5,4,4,5], target = 3

**Output:** -1

**Explanation:** We cannot find a sub-array of sum = 3.

**Example 5:**

**Input:** arr = [3,1,1,1,5,1,2,1], target = 3

**Output:** 3

**Explanation:** Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

This problem uses prefix sum and the Transactions Stock (At most k Transaction) idea.

At position i, we visualise as cutting the array into two partition. [0,1…i] and [i+1, i+2…]. For each i, we compute the total length of the subarrays (that sums to target) in these 2 partitions. For each i, we track the minimum length and return that.

`length = MIN {leftIndex[i] + rightIndex[i]} for each i value`

Hence, we need to first use the idea of prefix sum to obtain values at every i position for leftIndex and rightIndex.

*rightIndex[i] contains min length of subarray that sums up to target from position rightIndex.length-1, rightIndex.length-2,…i+1.*

*leftIndex[i] contains min length of subarray that sums up to target from position 0,1…i.*

## Leet Code 713. Subarray Product Less Than K

Your are given an array of positive integers `nums`

.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than `k`

.

**Example 1:**

**Input:** nums = [10, 5, 2, 6], k = 100

**Output:** 8

**Explanation:** The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].

Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

This is a Sliding Window Question.

## 1524. Number of Sub-arrays With Odd Sum

Given an array of integers `arr`

. Return *the number of sub-arrays* with **odd** sum.

As the answer may grow large, the answer **must be** computed modulo `10^9 + 7`

.

**Example 1:**

**Input:** arr = [1,3,5]

**Output:** 4

**Explanation:** All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]

All sub-arrays sum are [1,4,9,3,8,5].

Odd sums are [1,9,3,5] so the answer is 4.

**Example 2:**

**Input:** arr = [2,4,6]

**Output:** 0

**Explanation:** All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]

All sub-arrays sum are [2,6,12,4,10,6].

All sub-arrays have even sum and the answer is 0.

**Example 3:**

**Input:** arr = [1,2,3,4,5,6,7]

**Output:** 16

**Example 4:**

**Input:** arr = [100,100,99,99]

**Output:** 4

**Example 5:**

**Input:** arr = [7]

**Output:** 1

ODD — ODD = EVEN

ODD — EVEN = ODD

EVEN — ODD = ODD

EVEN — EVEN = EVEN

`class Solution {`

public int numOfSubarrays(int[] arr) {

// odd - odd = even

// odd - even = odd

// even - odd = odd

// even - even = even

int oddCount = 0;

int evenCount = 0;

int count = 0;

int sum=0;

int mod = (int)1e9 + 7;

for(int i=0; i<arr.length; i++){

sum+=arr[i];

int remainder = sum%2;

if(remainder<0){

remainder += 2;

}

if(remainder == 0){

count += (oddCount) % mod;

evenCount++;

} else {

count = (count+1) % mod;

count += (evenCount) % mod;

oddCount++;

}

}

return count % mod;

}

}

Hackerank Pairs

# Pairs

## LeetCode 5 Longest Palindrome Substring

Given a string `s`

, return *the longest palindromic substring* in `s`

.

**Example 1:**

**Input:** s = "babad"

**Output:** "bab"

**Note:** "aba" is also a valid answer.

**Example 2:**

**Input:** s = "cbbd"

**Output:** "bb"

This is actually complicated.

## Leet Code 516. Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

**Example 1:**

Input:

`"bbbab"`

Output:

`4`

One possible longest palindromic subsequence is “bbbb”.

**Example 2:**

Input:

`"cbbd"`

Output:

`2`

One possible longest palindromic subsequence is “bb”.

`class Solution {`

public int longestPalindromeSubseq(String s) {

int[][] dp = new int[s.length()][s.length()];

for(int i=0; i<s.length(); i++){

dp[i][i]=1;

}

for(int len=2; len<=s.length(); len++){

for(int i=0; i<=s.length()-len; i++){

int j=i+len-1;

if(s.charAt(i) == s.charAt(j)){

dp[i][j]=dp[i+1][j-1]+2;

} else {

dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);

}

}

}

return dp[0][s.length()-1];

}

}

- Initialised the diagonal values of the dp array to 1 (since a single character is always a palindrome)
- Variables i and j to represent the start and end indices of the subsequence being considered

Why is the formula **dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);**

Say we have string “agbdba”

When we are considering palindrome for length 3, we will check if a and b are the same. If not, then we either take ag or gb, to indicate this is the max length of subsequence.

ag -> 0,1, dp[i][j-1]

gb -> 1,2, dp[i+1][j]

agb -> 0,2, dp[i][j]

If we consider length 4, for 0–3 we will look at 0–2 or 1–3 indexes.

## Leet Code 9: Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

**Follow up:** Could you solve it without converting the integer to a string?

**Example 1:**

**Input:** x = 121

**Output:** true

**Example 2:**

**Input:** x = -121

**Output:** false

**Explanation:** From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

**Example 3:**

**Input:** x = 10

**Output:** false

**Explanation:** Reads 01 from right to left. Therefore it is not a palindrome.

**Example 4:**

**Input:** x = -101

**Output:** false

The first step is to find out the number of digits that the given input has and determine if it is an odd or even number.

Then, we add the last half of the digit into a number and compare with the first half.

Note that negative values are not palindromes.

**Leet Code Solution:**

`public class Solution {`

public bool IsPalindrome(int x) {

// Special cases:

// As discussed above, when x < 0, x is not a palindrome.

// Also if the last digit of the number is 0, in order to be a palindrome,

// the first digit of the number also needs to be 0.

// Only 0 satisfy this property.

if(x < 0 || (x % 10 == 0 && x != 0)) {

return false;

}

int revertedNumber = 0;

while(x > revertedNumber) {

revertedNumber = revertedNumber * 10 + x % 10;

x /= 10;

}

// When the length is an odd number, we can get rid of the middle digit by revertedNumber/10

// For example when the input is 12321, at the end of the while loop we get x = 12, revertedNumber = 123,

// since the middle digit doesn't matter in palidrome(it will always equal to itself), we can simply get rid of it.

return x == revertedNumber || x == revertedNumber/10;

}

}

## Leet Code 336. Palindrome Pairs (Hard)

Given a list of **unique** words, return all the pairs of the ** distinct** indices

`(i, j)`

in the given list, so that the concatenation of the two words `words[i] + words[j]`

is a palindrome.**Example 1:**

**Input:** words = ["abcd","dcba","lls","s","sssll"]

**Output:** [[0,1],[1,0],[3,2],[2,4]]

**Explanation:** The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

**Example 2:**

**Input:** words = ["bat","tab","cat"]

**Output:** [[0,1],[1,0]]

**Explanation:** The palindromes are ["battab","tabbat"]

**Example 3:**

**Input:** words = ["a",""]

**Output:** [[0,1],[1,0]]

The first solution is brute force where we go trough each pair of words and check if their concatenation forms a palindrome.

In the following solution, it is much simpler.

There are some cases that we need to consider.

- If a word is ABC, we check if it’s reverse CBA exists in the given words.
- If a word is an empty string, any string that is a palindrome will become a pair with it.
- Otherwise, we have XXBC string. Say, if XX is a palindrome, then if we can find CB in words, we will be able to form a pair. Hence, what we need to do is to check from position 0 to k and see if it is a palindrome, then we check if CB exists.
- Or, if we have CBXX string. Say if XX is palindrome, then we need to find BC in words to form a pair.

We make use of hashMap to help us.

`class Solution {`

public List<List<Integer>> palindromePairs(String[] words) {

List<List<Integer>> output = new ArrayList<>();

Map<String, Integer> lookup = new HashMap<>();

int n = words.length;

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

String word = words[i];

lookup.put(word, i);

}

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

String word = words[i];

if (word.equals("")) {

for (int j = 0; j < n; j++) {

if (i != j && isPal(words[j], 0, words[j].length() - 1)) {

output.add(Arrays.asList(i, j));

output.add(Arrays.asList(j, i));

}

}

continue;

}

String bw = new StringBuilder(word).reverse().toString(); // String builder is more efficient

if (lookup.containsKey(bw) && lookup.get(bw) != i) {

output.add(Arrays.asList(i, lookup.get(bw)));

}

for (int k = 1; k < word.length(); k++) {

if (isPal(word, 0, k - 1) && lookup.containsKey(new StringBuilder(word.substring(k)).reverse().toString())) {

output.add(Arrays.asList(lookup.get(new StringBuilder(word.substring(k)).reverse().toString()), i));

}

// Note the ordering is different from above

if (isPal(word, k, word.length() - 1) && lookup.containsKey(new StringBuilder(word.substring(0, k)).reverse().toString())) {

output.add(Arrays.asList(i, lookup.get(new StringBuilder(word.substring(0, k)).reverse().toString())));

}

}

}

return output;

}

private boolean isPal(String w, int st, int end) {

while (st < end) {

if (w.charAt(st) != w.charAt(end)) {

return false;

}

st++;

end--;

}

return true;

}

}

## 131. Palindrome Partitioning

Given a string `s`

, partition `s`

such that every substring of the partition is a **palindrome**. Return all possible palindrome partitioning of `s`

.

A **palindrome** string is a string that reads the same backward as forward.

**Example 1:**

**Input:** s = "aab"

**Output:** [["a","a","b"],["aa","b"]]

**Example 2:**

**Input:** s = "a"

**Output:** [["a"]]

The param index is the starting index.

O(n) complexity in each recursion call.

Max recursion depth is n — length of string. O(n) calls each.

Total complexity:

O(n*n)

Or…alternative solution

`class Solution {`

public List<List<String>> partition(String s) {

return partitionHelper(s);

}

public List<List<String>> partitionHelper(String s){

List<List<String>> result = new LinkedList<>();

for(int i=1; i<s.length()+1; i++){

String str = s.substring(0, i);

if(isPal(str)){

if (i==s.length()){

// the case where s is the entire string .. no need to recurse anymore

List<String> temp = new LinkedList<>();

temp.add(str);

result.add(temp);

} else {

List<List<String>> remainder = partitionHelper(s.substring(i));

if(remainder.size() != 0){

for(List<String> each: remainder){

each.add(0, str);

result.add(each);

}

}

}

}

}

return result;

}

public boolean isPal(String s){

int start = 0;

int end = s.length()-1;

while(start<end){

if(s.charAt(start) != s.charAt(end)) return false;

start++;

end--;

}

return true;

}

}

**How can we improve?**

We can further optimize the approach by using dynamic programming to determine if a string is a palindrome in constant time.

We use a 2 Dimensional array dp of size *N*⋅*N* where,

**dp[start][end] = true** , if the substring beginning at index start and ending at index end is a palindrome.

Otherwise, **dp[start][end] == false**.

Also, we must update the **dp array**, if we find that the current string is a palindrome.

## 132. Palindrome Partitioning II

Given a string `s`

, partition `s`

such that every substring of the partition is a palindrome.

Return *the **minimum** cuts needed for a palindrome partitioning of* `s`

.

**Example 1:**

`Input: s = "aab"`

Output: 1

Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

**Example 2:**

`Input: s = "a"`

Output: 0

**Example 3:**

`Input: s = "ab"`

Output: 1

class Solution {

int[] cutsDp;

boolean[][] palindromeDp;

public int minCut(String s) {

cutsDp = new int[s.length()]; // min cuts from 0 till i

palindromeDp = new boolean[s.length()][s.length()];

buildPalindromeDp(s, s.length());

for(int end=0; end<s.length(); end++){

int minimumCut=end;

for(int start=0; start<=end; start++){

if(palindromeDp[start][end]){

// no cut from position 0 to end

// Otherwise, the min cut will be to add 1 more (start to end) to the previous record for position

// from 0-(start-1)

minimumCut = start==0?0:Math.min(minimumCut, cutsDp[start-1]+1);

}

}

cutsDp[end]=minimumCut;

}

return cutsDp[s.length()-1];

}

public void buildPalindromeDp(String s, int n){

for(int end=0; end<s.length(); end++){

for(int start=0; start<=end; start++){

if(s.charAt(start)==s.charAt(end) && (end-start<=2 || palindromeDp[start+1][end-1])){

palindromeDp[start][end]=true;

}

}

}

}

}

`// WRONG, fails "abbab" because it does not go on to check abba for palindrome`

// once the palindrome check fails at "ab"

int numPartMin;

HashSet<String> visited;

public int minCut(String s) {

numPartMin = s.length()-1;

visited = new HashSet<>();

helper(s, 0);

return numPartMin;

}

public void helper(String s, int numPart){

System.out.println(s);

if(visited.contains(s)){

return;

}

if(s.length() == 0 || isPalim(s)){

numPartMin = Math.min(numPartMin, numPart);

return;

}

int end=1;

while(end < s.length() && isPalim(s.substring(0, end))){

end++;

}

visited.add(s);

helper(s.substring(end-1), numPart+1);

}

private boolean isPalim(String s){

int start=0;

int end = s.length()-1;

while(start<end){

if(s.charAt(start)!=s.charAt(end)){

return false;

}

start++;

end--;

}

return true;

}

## Increasing Triplet Subsequence

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there existsi, j, karr[i]

such that<arr[j]<arr[k]given 0 ≤i<j<k≤n-1 else return false.

**Note: **Your algorithm should run in O(*n*) time complexity and O(*1*) space complexity.

**Example 1:**

**Input: **[1,2,3,4,5]

**Output: **true

**Example 2:**

**Input: **[5,4,3,2,1]

**Output: **false

- If the current number is bigger than the secondSmallest, we know for sure that we have seen 3 increasing subsequence hence we can immediately return true.
- If the current number is between smallest and secondSmallest, then we need to update secondSmallest since that is no longer valid.
- If current number is smaller than smallest variable, then it means current smallest value is no longer valid. Hence we need to update it. We do not need to update secondSmallest because we know for sure that the current number is smaller than secondSmallest variable since we passed the first if.
**We do not update secondSmallest to hold the value of the previous smallest value (the one we just updated) because the ordering should be that smallest variable has lower index than secondSmallest.**In this case, if we update as seen in line 17, the index of the number in the secondSmallest variable is smaller than that in smallest variable, which is wrong. We want secondSmallest variable to hold the value with a greater index than the value in smallest variable.

- At this point, one question that comes to mind is that when in the third if loop if we only update the variable smallest, then wouldnt the ordering be wrong as well. Since we updated secondSmallest before we updated smallest variable, this means the index of secondSmallest value is smaller than index of smallest value. Then, you might try to do the screenshot below.

- But it doesnt work as well. It fails the test case here:

- The reason why it fails is because when we reach the -1, we update smallest = -1, secondSmallest = Integer.MAX_VALUE. Then we lost the [0,2,3] increasing subsequence since when we reach 3, we see that 3 is smaller than secondSmallest variable which holds max value and then we wrongly return False. In this case, perhaps the ordering does not matter much. As long as we know for sure that the secondSmallest variable contains a value that is bigger than at least 1 value that comes before it, we don’t have to update it. When we update the smallest variable in the 3rd If, we are simply making the smallest variable smaller but the two variables no longer contain the values of the increasing subsequence.

## Leetcode explanation

Another failed attempt. The solution here is logically correct but has time limit exceeded error.

`class Solution {`

public boolean increasingTriplet(int[] nums) {

int[] dp = new int[nums.length];

for(int n=0; n<nums.length; n++){

dp[n]=1;

for(int k=n-1; k>=0; k--){

if(nums[n]>nums[k]){

dp[n] = Math.max(dp[n], dp[k]+1);

if(dp[n] == 3) return true;

}

}

}

return false;

}

}

## Letter Combinations of a phone number

Given a string containing digits from `2-9`

inclusive, return all possible letter combinations that the number could represent. Return the answer in **any order**.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

**Example 1:**

**Input:** digits = "23"

**Output:** ["ad","ae","af","bd","be","bf","cd","ce","cf"]

**Example 2:**

**Input:** digits = ""

**Output:** []

**Example 3:**

**Input:** digits = "2"

**Output:** ["a","b","c"]

The idea is to make use of recursion to keep trying out all possible combinations of strings. The variable `position `

indicate which index of the input string `digits`

we are currently at. Each iteration is concerned with appending the given String variable `curr`

, accumulated from previous iterations with a single character String. This single character String is the possible value that the `position`

might represent (as we initialised in the HashMap).

When we have tried out all possible combinations, we will add the final string into the global list.

## Leet Code 153. Find Minimum in Rotated Sorted Array

Suppose an array of length `n`

sorted in ascending order is **rotated** between `1`

and `n`

times. For example, the array `nums = [0,1,2,4,5,6,7]`

might become:

`[4,5,6,7,0,1,2]`

if it was rotated`4`

times.`[0,1,2,4,5,6,7]`

if it was rotated`7`

times.

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]`

1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`

.

Given the sorted rotated array `nums`

, return *the minimum element of this array*.

**Example 1:**

**Input:** nums = [3,4,5,1,2]

**Output:** 1

**Explanation:** The original array was [1,2,3,4,5] rotated 3 times.

**Example 2:**

**Input:** nums = [4,5,6,7,0,1,2]

**Output:** 0

**Explanation:** The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

**Example 3:**

**Input:** nums = [11,13,15,17]

**Output:** 11

**Explanation:** The original array was [11,13,15,17] and it was rotated 4 times.

The big idea is to look at the pattern and figure out where exactly could the smallest value be located, when we are at the mid point of the array.

## Leetcode explanation

A very cool way of solving this problem is using the `Binary Search`

algorithm. In binary search we find out the mid point and decide to either search on the left or right depending on some condition.

Since the given array is sorted, we can make use of binary search. However, the array is rotated. So simply applying the binary search won’t work here.

In this question we would essentially apply a modified version of binary search where the `condition`

that decides the search direction would be different than in a standard binary search.

`// Another possible solution`

class Solution {

public int findMin(int[] nums) {

int low = 0;

int high = nums.length-1;

while(low<high){

int mid = (low+high)/2;

if(nums[mid]<nums[high]){

high=mid;

} else {

low=mid+1;

}

}

return nums[high];

}

}

// This solution works for 153 and 154...

class Solution {

public:

int findMin(vector<int>& nums) {

int lo = 0, hi = nums.size() - 1;

int best = -1;

while (lo <= hi) { // always the same cond

int mid = lo + (hi - lo) / 2; // always the same cond

if (nums[mid] > nums[hi]) {

lo = mid+1; // For sure, min is in range [mid+1, hi]

} else {

hi = hi-1;

best=mid; // might be best but not sure., may have better options on the right...try [slow, high-1]

}

}

return nums[best];

}

};

## Leet Code 154. Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `[0,1,2,4,5,6,7]`

might become `[4,5,6,7,0,1,2]`

).

Find the minimum element.

The array may contain duplicates.

**Example 1:**

**Input:** [1,3,5]

**Output:** 1

**Example 2:**

**Input:** [2,2,2,0,1]

**Output:** 0

`class Solution {`

public:

int findMin(vector<int>& nums) {

int lo = 0, hi = nums.size() - 1;

int best = -1;

while (lo <= hi) { // always the same cond

int mid = lo + (hi - lo) / 2; // always the same cond

if (nums[mid] > nums[hi]) {

lo = mid+1; // For sure, min is in range [mid+1, hi]

} else {

hi = hi-1;

best=mid; // might be best but not sure., may have better options on the right...try [slow, high-1]

}

}

return nums[best];

}

}; // also works for 153...

`0 rotation`

/

/

/

/

/

1 rotation

/

/^ if mid is here, for sure min is on the right. so we just shift the whole range.

/

/

/

/

/

/^

/ if mid is here, num[mid]<num[high], for sure min value is current

mid or on the left. So, we just high-- by 1 position.

2 rotations -> the last 2 elements in the prev arr moved to front

f /

e /

d /

c / (same structure)

b /^

a /^

i /

h /

g /

3 rotations -> Last 6 elements moved to front

f /

e /

d /

c / not moved. (same structure)

b / not moved

a / not moved

i /

h /

g /

We see that no matter how many rotations, the structure is always the same.

Hence the algorithm works. (I think i am correct)

The alphabets helps in identifying the /

## Leet Code 33. Search in Rotated Sorted Array

You are given an integer array `nums`

sorted in ascending order, and an integer `target`

.

Suppose that `nums`

is rotated at some pivot unknown to you beforehand (i.e., `[0,1,2,4,5,6,7]`

might become `[4,5,6,7,0,1,2]`

).

*If **target** is found in the array return its index, otherwise, return **-1**.*

**Example 1:**

**Input:** nums = [4,5,6,7,0,1,2], target = 0

**Output:** 4

**Example 2:**

**Input:** nums = [4,5,6,7,0,1,2], target = 3

**Output:** -1

**Example 3:**

**Input:** nums = [1], target = 0

**Output:** -1

`class Solution {`

public int search(int[] nums, int target) {

int start = 0, end = nums.length - 1;

while (start <= end) {

int mid = start + (end - start) / 2;

if (nums[mid] == target) return mid;

else if (nums[mid] >= nums[start]) {

if (target >= nums[start] && target < nums[mid]) end = mid - 1;

else start = mid + 1;

}

else {

if (target <= nums[end] && target > nums[mid]) start = mid + 1;

else end = mid - 1;

}

}

return -1;

}

}

## Leet Code 4. Median of Two Sorted Arrays

Given two sorted arrays `nums1`

and `nums2`

of size `m`

and `n`

respectively, return **the median** of the two sorted arrays.

**Follow up:** The overall run time complexity should be `O(log (m+n))`

.

**Example 1:**

**Input:** nums1 = [1,3], nums2 = [2]

**Output:** 2.00000

**Explanation:** merged array = [1,2,3] and median is 2.

**Example 2:**

**Input:** nums1 = [1,2], nums2 = [3,4]

**Output:** 2.50000

**Explanation:** merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

**Example 3:**

**Input:** nums1 = [0,0], nums2 = [0,0]

**Output:** 0.00000

**Example 4:**

**Input:** nums1 = [], nums2 = [1]

**Output:** 1.00000

**Example 5:**

**Input:** nums1 = [2], nums2 = []

**Output:** 2.00000

*This question is hard…*

- We want nums1 to contain the shorter array and nums2 to contain the longer array.
- We then do modified binary search on this smaller array.
- cut1 variable contains the number of elements in nums1 to the left of the cut made on num1 array. The first time we do, (0+len1)/2. In the array with 5 elements, it will be (0+5)/2 = 2.5 = 2. The first cut is after the second element at index 1.
- cut2 variable contains the number of elements in nums2 to the left of the cut made on num2 array. We calculate this from cut1 variable. Note that we want the cut to be at the median position. Median should be at half the length of the total len of the two arrays combined. For eg if we calculate median to be of length X, then since we previously calculated num1 to be contributing cut1 number to the left side of this median point, then num2 will contribute X-cut1 number of elements to the left side of this median point. Hence, we have X-num1 where X=(len+1)/2. The reason why it is (len+1) is so that if the total length of array is odd number, we want the left side of median to contain 1 more element than right side of the median.
- cut1==0 // no elements on left
- cut1==len1 // no elements on right
- With the cut determined, we then make sure that the condition holds
`l1<r2 and l2<r1`

- If this condition is violated (detected by the IF ELSE loops), then we need to modify the binary search low and high values in num1 array.
- If this condition is not violated, then we have reached the end and can return the median value.

## Leet Code 7 Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

**Note:**

Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

**Example 1:**

**Input:** x = 123

**Output:** 321

**Example 2:**

**Input:** x = -123

**Output:** -321

**Example 3:**

**Input:** x = 120

**Output:** 21

**Example 4:**

**Input:** x = 0

**Output:** 0

## Leet Code 88. Merge Sorted Array

Given two sorted integer arrays *nums1* and *nums2*, merge *nums2* into *nums1* as one sorted array.

**Note:**

- The number of elements initialized in
*nums1*and*nums2*are*m*and*n*respectively. - You may assume that
*nums1*has enough space (size that is**equal**to*m*+*n*) to hold additional elements from*nums2*.

**Example:**

Input:

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6], n = 3Output:[1,2,2,3,5,6]

## Leet Code 30. Substring with Concatenation of All Words

You are given a string `s`

and an array of strings `words`

of **the same length**. Return all starting indices of substring(s) in `s`

that is a concatenation of each word in `words`

**exactly once**, **in any order**, and **without any intervening characters**.

You can return the answer in **any order**.

**Example 1:**

**Input:** s = "barfoothefoobarman", words = ["foo","bar"]

**Output:** [0,9]

**Explanation:** Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.

The output order does not matter, returning [9,0] is fine too.

**Example 2:**

**Input:** s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]

**Output:** []

**Example 3:**

**Input:** s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]

**Output:** [6,9,12]

## Leet Code 31. Next Permutation

Implement **next permutation**, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be **in place** and use only constant extra memory.

**Example 1:**

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

**Output:** [1,3,2]

**Example 2:**

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

**Output:** [1,2,3]

**Example 3:**

**Input:** nums = [1,1,5]

**Output:** [1,5,1]

**Example 4:**

**Input:** nums = [1]

**Output:** [1]

This question is quite hard. Need to spot the pattern.

**Leet code given solution:**

First, we observe that a sequence in descending order has no next larger permutation.

We need to find the first pair of two successive numbers a[i]and a[i-1], from the right, which satisfy** a[i-1] < a[i]**. For eg,

Now, no rearrangements to the right of a[i-1] (section XXX)can create a larger permutation since that subarray consists of numbers in descending order.**36XXX** where 6 is larger than 3.

We want to create the permutation just larger than the current one. Therefore, we need to** replace the number a[i-1] with the number which is just larger than itself among the numbers lying to its right section**, say a[j], one of x.

We **swap the numbers a[i-1] and a[j]**. We now have the correct number at index i-1. But still the current permutation isn’t the permutation that we are looking for. We need the smallest permutation that can be formed by using the numbers only to the right of a[i-1]. Therefore, **we need to place those numbers in ascending order to get their smallest permutation. **Therefore, we simply need to **reverse the numbers following a[i-1]** to get the next smallest lexicographic permutation.

`class Solution {`

public void nextPermutation(int[] nums) {

int i = nums.length - 2;

while(i>=0 && nums[i+1]<=nums[i]){

i--;

}

if(i>=0){

// current i is the index where nums[i] < nums[i+1]

int j = nums.length-1;

// from right to left, get the first number smaller than nums[i]

while(j>=i && nums[j]<=nums[i]){

j--;

}

swap(nums, i, j);

}

reverse(nums, i+1);

}

private void reverse(int[] nums, int start){

int i = start, j = nums.length-1;

while(i<j){

swap(nums, i, j);

j--;

i++;

}

}

private void swap(int[] nums, int i, int j){

int temp = nums[i];

nums[i]=nums[j];

nums[j]=temp;

}

}

## Leet Code 35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

**Example 1:**

**Input:** nums = [1,3,5,6], target = 5

**Output:** 2

**Example 2:**

**Input:** nums = [1,3,5,6], target = 2

**Output:** 1

**Example 3:**

**Input:** nums = [1,3,5,6], target = 7

**Output:** 4

**Example 4:**

**Input:** nums = [1,3,5,6], target = 0

**Output:** 0

**Example 5:**

**Input:** nums = [1], target = 0

**Output:** 0

## Leet Code 36 Valid Sudoku

Determine if a `9 x 9`

Sudoku board is valid. Only the filled cells need to be validated **according to the following rules**:

- Each row must contain the digits
`1-9`

without repetition. - Each column must contain the digits
`1-9`

without repetition. - Each of the nine
`3 x 3`

sub-boxes of the grid must contain the digits`1-9`

without repetition.

**Note:**

- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.

**Leet Code Solution**:

One could use

`box_index = (row / 3) * 3 + col / 3`

where`/`

is an integer division,`row`

is a row number, and`col`

is a column number.

`class Solution {`

public boolean isValidSudoku(char[][] board) {

HashSet<Integer> [] rows = new HashSet[9];

HashSet<Integer> [] columns = new HashSet[9];

HashSet<Integer> [] boxes = new HashSet[9];

for(int i=0; i<9; i++){

rows[i]=new HashSet<Integer>();

columns[i]=new HashSet<Integer>();

boxes[i]=new HashSet<Integer>();

}

for(int i=0; i<9; i++){

for(int j=0; j<9; j++){

char num = board[i][j];

if(num != '.'){

int n = (int)num;

int boxIndex = (i/3)*3+j/3; // How to get this formula?

if(rows[i].contains(n) || columns[j].contains(n) || boxes[boxIndex].contains(n)) return false;

rows[i].add(n);

columns[j].add(n);

boxes[boxIndex].add(n);

}

}

}

return true;

}

}

The expression `(i/3)`

represents the index of the row block that the cell belongs to. There are three row blocks in a Sudoku puzzle, each containing three rows.

The expression `(j/3)`

represents the index of the column block that the cell belongs to. There are three column blocks in a Sudoku puzzle, each containing three columns.

The expression `(i/3)*3`

maps the row block index to the starting row index of the block. Each row block contains three rows. So, to get the index of the first row of the block, we need to multiply the row block index by 3. For example, if `i=4`

, then `(i/3)*3=3`

, which is the index of the first row of the second row block. If `i=5`

, then `(i/3)*3=3`

, which is again the index of the first row of the second row block.

Without the multiplication by 3, the formula `(i/3)`

would give us the index of the row block, but not the index of the first row of the block. By multiplying by 3, we shift the index to the first row of the block.

## 41. First Missing Positive (Hard)

Given an unsorted integer array `nums`

, find the smallest missing positive integer.

**Follow up:** Could you implement an algorithm that runs in `O(n)`

time and uses constant extra space.?

**Example 1:**

**Input:** nums = [1,2,0]

**Output:** 3

**Example 2:**

**Input:** nums = [3,4,-1,1]

**Output:** 2

**Example 3:**

**Input:** nums = [7,8,9,11,12]

**Output:** 1

`class Solution {`

public int firstMissingPositive(int[] nums) {

int n = nums.length;

// Base case.

int contains = 0;

for (int i = 0; i < n; i++)

if (nums[i] == 1) {

contains++;

break;

}

if (contains == 0)

return 1;

// Replace negative numbers, zeros,

// and numbers larger than n by 1s.

// After this convertion nums will contain

// only positive numbers.

for (int i = 0; i < n; i++)

if ((nums[i] <= 0) || (nums[i] > n))

nums[i] = 1;

// Use index as a hash key and number sign as a presence detector.

// For example, if nums[1] is negative that means that number `1`

// is present in the array.

// If nums[2] is positive - number 2 is missing.

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

int a = Math.abs(nums[i]);

// If you meet number a in the array - change the sign of a-th element.

// Be careful with duplicates : do it only once.

if (a == n)

nums[0] = - Math.abs(nums[0]);

else

nums[a] = - Math.abs(nums[a]);

}

// Now the index of the first positive number

// is equal to first missing positive.

for (int i = 1; i < n; i++) {

if (nums[i] > 0)

return i;

}

if (nums[0] > 0)

return n;

return n + 1;

}

}

O(N) time complexity.

## 218. The Skyline Problem

A city’s **skyline** is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return *the **skyline** formed by these buildings collectively*.

The geometric information of each building is given in the array `buildings`

where `buildings[i] = [lefti, righti, heighti]`

:

`lefti`

is the x coordinate of the left edge of the`ith`

building.`righti`

is the x coordinate of the right edge of the`ith`

building.`heighti`

is the height of the`ith`

building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height `0`

.

The **skyline** should be represented as a list of “key points” **sorted by their x-coordinate** in the form `[[x1,y1],[x2,y2],...]`

. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate `0`

and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

**Note:** There must be no consecutive horizontal lines of equal height in the output skyline. For instance, `[...,[2 3],[4 5],[7 5],[11 5],[12 7],...]`

is not acceptable; the three lines of height 5 should be merged into one in the final output as such: `[...,[2 3],[4 5],[12 7],...]`

**Example 1:**

**Input:** buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]

**Output:** [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

**Explanation:**

Figure A shows the buildings of the input.

Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

**Example 2:**

**Input:** buildings = [[0,2,3],[2,5,3]]

**Output:** [[0,3],[5,0]]

Leet Code Solution:

Copied from a YouTube tutorial on this question.

The idea is to maintain 2 data structures: (1) TreeMap where the key indicates the X-Coord, Value is an ArrayList of int array of values (start, end, height). This array list of int arrays are buildings that start with the key X Coord. (2) Max Heap which contains the height of all the buildings. As we iterate through the Tree Map, we will update this Max Heap. At any point, the max heap will contain the heights of all the buildings presently at the key value (X-Coord) we are iterating at in the Tree Map.

`class Solution {`

public List<List<Integer>> getSkyline(int[][] buildings) {

// TreeMap: Key: X-coord. Value: ArrayList of Int values

// Max heap: height of all buildings

TreeMap<Integer, List<int[]>> map = new TreeMap<>();

for(int[] build: buildings){

map.putIfAbsent(build[0], new ArrayList<>());

map.putIfAbsent(build[1], new ArrayList<>());

map.get(build[0]).add(build);

map.get(build[1]).add(build);

}

PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[2]-a[2]);

List<List<Integer>> results = new ArrayList<>();

for(int xCoord: map.keySet()){

List<int[]> bs = map.get(xCoord);

for(int[] b: bs){

if(b[0] == xCoord){

// start point

maxHeap.offer(b);

} else {

// end point

maxHeap.remove(b);

}

}

if (maxHeap.size()==0){

List<Integer> temp = new ArrayList<>();

temp.add(xCoord);

temp.add(0);

results.add(temp);

} else {

int maxHeight = maxHeap.peek()[2];

if(results.size()==0 || results.get(results.size()-1).get(1) != maxHeight){

List<Integer> temp = new ArrayList<>();

temp.add(xCoord);

temp.add(maxHeight);

results.add(temp);

}

}

}

return results;

}

}

## 807. Max Increase to Keep City Skyline

There is a city composed of `n x n`

blocks, where each block contains a single building shaped like a vertical square prism. You are given a **0-indexed** `n x n`

integer matrix `grid`

where `grid[r][c]`

represents the **height** of the building located in the block at row `r`

and column `c`

.

A city’s **skyline** is the outer contour formed by all the building when viewing the side of the city from a distance. The **skyline** from each cardinal direction north, east, south, and west may be different.

We are allowed to increase the height of **any number of buildings by any amount** (the amount can be different per building). The height of a `0`

-height building can also be increased. However, increasing the height of a building should **not** affect the city's **skyline** from any cardinal direction.

Return *the **maximum total sum** that the height of the buildings can be increased by **without** changing the city’s **skyline** from any cardinal direction*.

**Example 1:**

`Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]`

Output: 35

Explanation: The building heights are shown in the center of the above image.

The skylines when viewed from each cardinal direction are drawn in red.

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],

[7, 4, 7, 7],

[9, 4, 8, 7],

[3, 3, 3, 3] ]

**Example 2:**

`Input: grid = [[0,0,0],[0,0,0],[0,0,0]]`

Output: 0

Explanation: Increasing the height of any building will result in the skyline changing.

`class Solution {`

public int maxIncreaseKeepingSkyline(int[][] grid) {

// as long as it is not the max in its col or row, we can increase it

int[] row = new int[grid.length];

int[] col = new int[grid[0].length];

for(int i=0; i<grid.length; i++){

for(int j=0; j<grid[0].length; j++){

row[i]=Math.max(row[i], grid[i][j]);

col[j]=Math.max(col[j], grid[i][j]);

}

}

int val = 0;

for(int i=0; i<grid.length; i++){

for(int j=0; j<grid[0].length; j++){

if(grid[i][j]<row[i] && grid[i][j]<col[j]){

val += Math.min(row[i], col[j])-grid[i][j];

}

}

}

return val;

}

}

## Leet Code 295. Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

`[2,3,4]`

, the median is `3`

`[2,3]`

, the median is `(2 + 3) / 2 = 2.5`

Design a data structure that supports the following two operations:

- void addNum(int num) — Add a integer number from the data stream to the data structure.
- double findMedian() — Return the median of all elements so far

# 480. Sliding Window Median

The **median** is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

- For examples, if
`arr = [2,3,4]`

, the median is`3`

. - For examples, if
`arr = [1,2,3,4]`

, the median is`(2 + 3) / 2 = 2.5`

.

You are given an integer array `nums`

and an integer `k`

. There is a sliding window of size `k`

which is moving from the very left of the array to the very right. You can only see the `k`

numbers in the window. Each time the sliding window moves right by one position.

Return *the median array for each window in the original array*. Answers within `10-5`

of the actual value will be accepted.

**Example 1:**

`Input: nums = [1,3,-1,-3,5,3,6,7], k = 3`

Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]

Explanation:

Window position Median

--------------- -----

[1 3 -1] -3 5 3 6 7 1

1 [3 -1 -3] 5 3 6 7 -1

1 3 [-1 -3 5] 3 6 7 -1

1 3 -1 [-3 5 3] 6 7 3

1 3 -1 -3 [5 3 6] 7 5

1 3 -1 -3 5 [3 6 7] 6

**Example 2:**

`Input: nums = [1,2,3,4,2,3,1,4,2], k = 3`

Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

`class Solution {`

PriorityQueue<Integer> maxHeap; // 1st part

PriorityQueue<Integer> minHeap; // 2nd part

public Solution() {

// use Collections.reverseOrder() as comparator as this will work when input number as max integer, can't use (a,b)->b-a

maxHeap = new PriorityQueue<>(Collections.reverseOrder());

minHeap = new PriorityQueue<>();

}

void addNum(int n) {

if(maxHeap.size()==0 || n <= maxHeap.peek()) {

maxHeap.offer(n);

} else {

minHeap.offer(n);

}

rebalance();

}

void remove(int num) {

if(num <= maxHeap.peek()) maxHeap.remove(num);

else minHeap.remove(num);

rebalance();

}

void rebalance() {

if(minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());

// max heap can have one extra node than min heap, as we will use for returning the median when total input size is odd number

else if(maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());

}

double findMedian() {

if(maxHeap.size() == minHeap.size()) return maxHeap.peek()/2.0 + minHeap.peek() /2.0;

else return maxHeap.peek();

}

public double[] medianSlidingWindow(int[] nums, int k) {

int start = 0;

double[] result = new double[nums.length - k + 1 ];

for(int end=0; end < nums.length; end++) {

addNum(nums[end]);

if(end + 1 >= k) {// shrink the window & calculate the median

result[start] = findMedian();

remove(nums[start]); // remove the start number as we move forward the next window size

start++; // move start window ahead

}

}

return result;

}

}

## 2387. Median of a Row Wise Sorted Matrix

Given an `m x n`

matrix `grid`

containing an **odd** number of integers where each row is sorted in **non-decreasing** order, return *the **median** of the matrix*.

You must solve the problem in less than `O(m * n)`

time complexity.

**Example 1:**

`Input: grid = [[1,1,2],[2,3,3],[1,3,4]]`

Output: 2

Explanation: The elements of the matrix in sorted order are 1,1,1,2,2,3,3,3,4. The median is 2.

**Example 2:**

`Input: grid = [[1,1,3,3,4]]`

Output: 3

Explanation: The elements of the matrix in sorted order are 1,1,3,3,4. The median is 3.

`class Solution {`

public int matrixMedian(int[][] grid) {

int m=grid.length;

int n=grid[0].length;

int low=0;

int high = (int)Math.pow(10, 6)+1;

while(low<high){

int mid = low + (high-low) / 2;

if(fulfill(mid, grid)){

high = mid; // try and see if can go lower...

} else {

low = mid + 1;

}

}

return high;

}

// returns true if the number of elements that are <= s is n*m/2+1.

// Half the numbers in the grid is greater or equal to s.

public boolean fulfill(int s, int[][] grid){

int res = 0;

for(int[] row: grid){

res+=bisectRight(row, s);

}

return res >= (grid.length * grid[0].length) / 2 + 1;

}

public int bisectRight(int[] row, int target){

int index = Arrays.binarySearch(row, target);

if (index < 0) {

index = -(index + 1);

} else {

// If the target element is found, move to the next index

// We need to get the rightmost index if there are multiple

// similar values

while (index < row.length && row[index] == target) {

index++;

}

}

return index;

}

}

## Leet Code 249. Group Shifted Strings (Medium)

Given a string, we can “shift” each of its letter to its successive letter, for example: `"abc" -> "bcd"`

. We can keep "shifting" which forms the sequence:

`"abc" -> "bcd" -> ... -> "xyz"`

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: `["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]`

,

A solution is:

`[`

["abc","bcd","xyz"],

["az","ba"],

["acef"],

["a","z"]

]

Two strings are considered to be in the same group if we can shift those strings and get to the same string. The idea to solve this question is to compute the difference between each character in a string, then store them in a stack. For eg, if i have a word “abe” then the stack will contain [1,3]. We have a global hash map where the key would be the stack of integers and the values would be a list of string that has this key stack.

Note that we have to check if the difference is smaller than 0 and add 26 to it. This is because we need to account for wrapping…

Below is a tried and tested code.

`class Solution {`

public List<List<String>> groupStrings(String[] strings) {

List<List<String>> result = new LinkedList<>();

Map<String, List<String>> map = new HashMap<>();

for(String str: strings){

String diffString = "";

for(int i=1; i<str.length(); i++){

int newDiff = Character.getNumericValue(str.charAt(i)) - Character.getNumericValue(str.charAt(i-1));

if(newDiff<0){

newDiff+=26;

}

diffString += "#" + newDiff;

}

map.putIfAbsent(diffString, new ArrayList<>());

map.get(diffString).add(str);

}

for(List<String> each: map.values()){

result.add(each);

}

return result;

}

}

## Leet Code 76. Minimum Window Substring (Hard)

Given two strings `s`

and `t`

, return *the minimum window in **s** which will contain all the characters in *

. If there is no such window in *t*`s`

that covers all characters in `t`

, return *the empty string *

.*""*

**Note** that If there is such a window, it is guaranteed that there will always be only one unique minimum window in `s`

.

**Example 1:**

**Input:** s = "ADOBECODEBANC", t = "ABC"

**Output:** "BANC"

**Example 2:**

**Input:** s = "a", t = "a"

**Output:** "a"

This is the sliding window method.

## 345. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

**Example 1:**

**Input: **"hello"

**Output: **"holle"

**Example 2:**

**Input: **"leetcode"

**Output: **"leotcede"

`// Or this...`

class Solution {

public String reverseVowels(String s) {

HashSet<Character> set = new HashSet<>();

set.add('a');

set.add('e');

set.add('i');

set.add('o');

set.add('u');

set.add('A');

set.add('E');

set.add('I');

set.add('O');

set.add('U');

String reversed = "";

for(int i=0; i<s.length(); i++){

if(set.contains(s.charAt(i))){

reversed = s.substring(i, i+1) + reversed;

}

}

System.out.println(reversed);

int index = 0;

for(int i=0; i<s.length(); i++){

if(set.contains(s.charAt(i))){

String end = "";

if(index+1 < s.length()){

end = s.substring(i+1);

}

s = s.substring(0, i)+reversed.substring(index, index+1)+ end;

index++;

}

}

return s;

}

}

## Leet Code 829. Consecutive Numbers Sum

Given a positive integer `N`

, how many ways can we write it as a sum of consecutive positive integers?

**Example 1:**

**Input: **5

**Output: **2

**Explanation: **5 = 5 = 2 + 3

**Example 2:**

**Input: **9

**Output: **3

**Explanation: **9 = 9 = 4 + 5 = 2 + 3 + 4

**Example 3:**

**Input: **15

**Output: **4

**Explanation: **15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Using prefix sum method works for some of the test cases but fails for others when the number gets big. This is due to Integer overflow. Nevertheless, i will still put my attempt.

The correct Solution: Too complicated to understand, seriously….`TODO`

## 151. Reverse Words in a String

Given an input string `s`

, reverse the order of the **words**.

A **word** is defined as a sequence of non-space characters. The **words** in `s`

will be separated by at least one space.

Return *a string of the words in reverse order concatenated by a single space.*

**Note** that `s`

may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

**Example 1:**

**Input:** s = "the sky is blue"

**Output:** "blue is sky the"

**Example 2:**

**Input:** s = " hello world "

**Output:** "world hello"

**Explanation:** Your reversed string should not contain leading or trailing spaces.

**Example 3:**

**Input:** s = "a good example"

**Output:** "example good a"

**Explanation:** You need to reduce multiple spaces between two words to a single space in the reversed string.

**Example 4:**

**Input:** s = " Bob Loves Alice "

**Output:** "Alice Loves Bob"

**Example 5:**

**Input:** s = "Alice does not even like bob"

**Output:** "bob like even not does Alice"

The idea is to reverse the given string. Then, for each word segment separated by space, we reverse the word.

Since the given string might have spacing (extra) between words or outside of the sentence, we need to remove them.

`class Solution {`

public String reverseWords(String s) {

String trimmed = s.trim();

String[] splitWord = trimmed.split(" ");

String result = "";

for(int i=splitWord.length-1; i>=0; i--){

if(splitWord[i].isEmpty()) continue;

result+=splitWord[i].trim()+" ";

}

return result.trim();

}

}

## 186. Reverse Words in a String II

Given a character array `s`

, reverse the order of the **words**.

A **word** is defined as a sequence of non-space characters. The **words** in `s`

will be separated by a single space.

Your code must solve the problem **in-place,** i.e. without allocating extra space.

**Example 1:**

`Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]`

Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

**Example 2:**

`Input: s = ["a"]`

Output: ["a"]

`class Solution {`

public void reverseWords(char[] s) {

reverse(s, 0, s.length-1);

int start=0;

while(start<s.length){

int end = start;

while(end<s.length && s[end] != ' '){

end++;

}

reverse(s, start, end-1);

start = end+1;

}

}

private void reverse (char[] s, int start, int end){

while(start<end){

char tmp = s[start];

s[start]=s[end];

s[end]=tmp;

start++;

end--;

}

}

}

The idea is to reverse the entire string first, then reverse each individual word.

## 209. Minimum Size Subarray Sum

Given an array of **n** positive integers and a positive integer **s**, find the minimal length of a **contiguous** subarray of which the sum ≥ **s**. If there isn’t one, return 0 instead.

**Example:**

**Input:** s = 7, nums = [2,3,1,2,4,3]

**Output:** 2

**Explanation: **the subarray [4,3] has the minimal length under the problem constraint.

Sort of like sliding window.

The thing to note is line 18. We compute the length to be end — start instead of (end-start+1), this is because the end index would be incremented by 1 and then it fails the while condition. This means the end index is not valid/not included in making the sum.

Below is a brute force solution . Think about it, we don’t actually need to keep recomputing sum…so we should follow up to improve this algorithm using sliding window and storing a sum counter.

`for(int i=0; i<nums.length; i++){`

int j=i;

int sum = 0;

while(sum<target && j<nums.length){

sum+=nums[j];

j++;

}

if(sum>=target){

minLength = Math.min(minLength, j-i);

}

}

## 1679. Max Number of K-Sum Pairs

You are given an integer array `nums`

and an integer `k`

.

In one operation, you can pick two numbers from the array whose sum equals `k`

and remove them from the array.

Return *the maximum number of operations you can perform on the array*.

**Example 1:**

**Input:** nums = [1,2,3,4], k = 5

**Output:** 2

**Explanation:** Starting with nums = [1,2,3,4]:

- Remove numbers 1 and 4, then nums = [2,3]

- Remove numbers 2 and 3, then nums = []

There are no more pairs that sum up to 5, hence a total of 2 operations.

**Example 2:**

**Input:** nums = [3,1,3,4,3], k = 6

**Output:** 1

**Explanation:** Starting with nums = [3,1,3,4,3]:

- Remove the first two 3's, then nums = [1,4,3]

There are no more pairs that sum up to 6, hence a total of 1 operation.

This question is just finding the number of pairs that adds up to k. Even though they have “max”, it is not really a DP question…because the ordering of the selecting pairs, considering numbers in the arr does not matter.

## 348. Design Tic-Tac-Toe

Design a Tic-tac-toe game that is played between two players on a nxn grid.

You may assume the following rules:

- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves is allowed.
- A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

The O(n²) algorithm is pretty easy to derive….but can we do better?

`// Correct solution that passes all TCs`

class TicTacToe {

int[][] board;

public TicTacToe(int n) {

board = new int[n][n];

}

public int move(int row, int col, int player) {

board[row][col]=player;

return getWinner(row, col, player);

}

// For every move, check if the row/col contains any winner

public int getWinner(int row, int col, int player){

// check entire row

int countRow=0;

for(int i=0; i<board.length; i++){

if(board[row][i] == player){

countRow ++;

} else {

break;

}

}

if(countRow == board.length) return player;

// check entire col

int countCol=0;

for(int i=0; i<board.length; i++){

if(board[i][col] == player){

countCol ++;

} else {

break;

}

}

if(countCol == board.length) return player;

// LEFT TO RIGHT DIAGONAL

// check upp diagonal

int i = row;

int j = col;

int countUppDiag = 0;

while(i >= 0 && j >= 0){

if(board[i][j] == player){

countUppDiag ++;

} else {

break;

}

i--;

j--;

}

// check bottom diagonal

int i2 = row+1;

int j2 = col+1;

int countBotDiag = 0;

while(i2 < board.length && j2 < board.length){

if(board[i2][j2] == player){

countBotDiag ++;

} else {

break;

}

i2++;

j2++;

}

if((countBotDiag+countUppDiag) == board.length) return player;

// RIGHT TO LEFT INFLATION

// check upp diagonal

int i3 = row;

int j3 = col;

int countUppDiagRight = 0;

while(i3 >= 0 && j3 <board.length){

if(board[i3][j3] == player){

countUppDiagRight ++;

} else {

break;

}

i3--;

j3++;

}

// check bottom diagonal

int i4 = row+1;

int j4 = col-1;

int countBotDiagRight = 0;

while(i4 < board.length && j4 >=0){

if(board[i4][j4] == player){

countBotDiagRight ++;

} else {

break;

}

i4++;

j4--;

}

if((countUppDiagRight+countBotDiagRight) == board.length) return player;

return 0;

}

}

/**

* Your TicTacToe object will be instantiated and called as such:

* TicTacToe obj = new TicTacToe(n);

* int param_1 = obj.move(row,col,player);

*/

## 1498. Number of Subsequences That Satisfy the Given Sum Condition

Given an array of integers `nums`

and an integer `target`

.

Return the number of **non-empty** subsequences of `nums`

such that the sum of the minimum and maximum element on it is less or equal to `target`

. Since the answer may be too large, return it modulo `109 + 7`

.

**Example 1:**

**Input:** nums = [3,5,6,7], target = 9

**Output:** 4

**Explanation: **There are 4 subsequences that satisfy the condition.

[3] -> Min value + max value <= target (3 + 3 <= 9)

[3,5] -> (3 + 5 <= 9)

[3,5,6] -> (3 + 6 <= 9)

[3,6] -> (3 + 6 <= 9)

**Example 2:**

**Input:** nums = [3,3,6,8], target = 10

**Output:** 6

**Explanation: **There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).

[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

**Example 3:**

**Input:** nums = [2,3,3,4,6,7], target = 12

**Output:** 61

**Explanation: **There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).

Number of valid subsequences (63 - 2 = 61).

**Example 4:**

**Input:** nums = [5,2,4,1,7,6,8], target = 16

**Output:** 127

**Explanation: **All non-empty subset satisfy the condition (2^7 - 1) = 127

## Leetcode answer: Binary search

## Intuition

Starting from the brute-force approach, if we simply generate all possible subsequences and then iterate through each subsequence to find its maximum and minimum elements, this approach is feasible but the time complexity will be very high.

Assuming the size of the array is `n`

, we will have O(2^n) non-empty subsequences, resulting in a time complexity of O(2^n.n). This method is very expensive and indicates that we need a more efficient way to traverse the subsequence.

Note that we only need to consider the minimum and maximum elements of a subsequence to determine whether it is valid, and elements with values between them do not affect our judgment. Therefore, we can traverse all possible `(minimum, maximum)`

combinations and check if they are valid.

If there are `k`

subsequences with `min`

as the minimum value and `max`

as the maximum value, we only need to check if `min + max <= target`

. The number of such subsequences `k`

depends on how many elements have values that are between `min`

and `max`

. Therefore, we need to sort `nums`

first, so that the number of values between `min`

and `max`

can be represented by their index difference.

Here, we let `left`

and `right`

be the pointers to the minimum element and the maximum element. That is `nums[left] = min`

.

Now we need to traverse each possible minimum value. For `min = nums[left]`

, we need to ensure that the subsequences with this number as the minimum value are valid, which means the maximum element of these subsequences cannot be greater than `target-nums[left]`

. In other words, we need to find the largest element that is not greater than `target-nums[left]`

. As shown in the picture below, we have found that `nums[right] = 12`

is the rightmost element that is smaller than or equal to `17 - nums[left]`

, then we can freely pick elements within the range `[left + 1, right]`

to make valid subsequences.

Since the array is already sorted, we can use binary search to find the insertion position of `target - nums[left]`

. Note that we are looking for the rightmost element that is smaller than or equal to `target - nums[left]`

, and the binary search finds the index of the smallest element that is larger than `target - nums[left]`

. Therefore, once we find the rightmost insertion position as `k`

, we have `right = k - 1`

.

Now we have the left and right indices `left`

and `right`

. For each number in the range `[left + 1, right]`

, there are 2 options: we can either take it or not take it, so there are a total of 2^(right - left) valid subsequences that have `nums[left]`

as the minimum element.

Next, we move to the next `min`

by moving the left pointer `left`

one step to the right. We repeat the process by using binary search to find the new insertion position of `target - nums[left]`

.

Sometimes we may encounter situations where `left > right`

and we don't need to consider these subsequences because they have already been calculated before and there is no need to recalculate them again.

## Algorithm

- Initialize
`answer = 0`

and the length of`nums`

as`n`

. - Iterate over the left index
`left`

from`0`

to`n - 1`

, for each index`left`

:

- Use binary search to locate the rightmost index
`right`

which`nums[right] <= target - nums[left]`

. - If
`left <= right`

, count the total number of valid subsequences as 2right - left2 ^ {\text{right - left}}2right - left - Increment
`answer`

by the number of valid subsequences.

3. Return `answer`

once the iteration ends.

`class Solution {`

public static int binarySearchRightmost(int[] nums, int target) {

int left = 0, right = nums.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (nums[mid] <= target) {

left = mid + 1;

} else {

right = mid - 1;

}

}

return left;

}

public int numSubseq(int[] nums, int target) {

int n = nums.length;

int mod = 1_000_000_007;

Arrays.sort(nums);

int[] power = new int[n];

power[0] = 1;

for (int i = 1; i < n; ++i) {

power[i] = (power[i - 1] * 2) % mod;

}

int answer = 0;

// Iterate over each left pointer.

for (int left = 0; left < n; left++) {

// Find the insertion position for `target - nums[left]`

// 'right' equals the insertion index minus 1.

int right = binarySearchRightmost(nums, target - nums[left]) - 1;

if (right >= left) {

answer += power[right - left];

answer %= mod;

}

}

return answer;

}

}

The code initializes an integer array named `power`

with `n`

elements. It then sets the first element of the array to `1`

. The purpose of the code is to generate a sequence of powers of two modulo a given `mod`

value, where `mod`

is an integer. The code achieves this by using a for-loop that iterates from index `1`

to `n-1`

of the array. In each iteration, the code sets the value of `power[i]`

to be twice the previous element in the array `power[i-1]`

, but with the result modulo `mod`

.

In other words, the `power`

array will contain the sequence of powers of 2 modulo `mod`

from `2^0`

to `2^(n-1)`

. The modulo operation is used to ensure that the result stays within the range of integers that can be represented by the variable type used.

## 1052. Grumpy Bookstore Owner

Today, the bookstore owner has a store open for `customers.length`

minutes. Every minute, some number of customers (`customers[i]`

) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, `grumpy[i] = 1`

, otherwise `grumpy[i] = 0`

. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for `X`

minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

**Example 1:**

**Input: **customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3

**Output: **16

**Explanation:** The bookstore owner keeps themselves not grumpy for the last 3 minutes.

The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

`class Solution {`

int sum = 0;

for(int i=0; i<customers.length; i++){

if(grumpy[i]==0 || i<minutes){

sum+=customers[i];

}

}

int max = sum;

int start=0;

int end = minutes;

while(end <= customers.length-1){

if(grumpy[end] == 1){

sum+=customers[end];

}

if(grumpy[start]==1){

sum-=customers[start];

}

max = Math.max(max, sum);

end++;

start++;

}

return max;

}

# 1743. Restore the Array From Adjacent Pairs

There is an integer array `nums`

that consists of `n`

**unique **elements, but you have forgotten it. However, you do remember every pair of adjacent elements in `nums`

.

You are given a 2D integer array `adjacentPairs`

of size `n - 1`

where each `adjacentPairs[i] = [ui, vi]`

indicates that the elements `ui`

and `vi`

are adjacent in `nums`

.

It is guaranteed that every adjacent pair of elements `nums[i]`

and `nums[i+1]`

will exist in `adjacentPairs`

, either as `[nums[i], nums[i+1]]`

or `[nums[i+1], nums[i]]`

. The pairs can appear **in any order**.

Return *the original array *`nums`

*. If there are multiple solutions, return *** any of them**.

**Example 1:**

`Input: adjacentPairs = [[2,1],[3,4],[3,2]]`

Output: [1,2,3,4]

Explanation: This array has all its adjacent pairs in adjacentPairs.

Notice that adjacentPairs[i] may not be in left-to-right order.

**Example 2:**

`Input: adjacentPairs = [[4,-2],[1,4],[-3,1]]`

Output: [-2,4,1,-3]

Explanation: There can be negative numbers.

Another solution is [-3,1,4,-2], which would also be accepted.

**Example 3:**

`Input: adjacentPairs = [[100000,-100000]]`

Output: [100000,-100000]

`class Solution {`

public:

vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {

unordered_map<int, vector<int>> map; // bidirectional connection

for (const auto& pair : adjacentPairs) {

int first = pair[0];

int second = pair[1];

map[first].emplace_back(second); //replace or update

map[second].emplace_back(first);

}

// find the element that only has 1 count. it is either the head or tail.

int root=-1;

for(auto it=map.begin(); it!=map.end(); it++){

if(it->second.size() == 1){

root=it->first;

break;

}

}

set<int> visited;

vector<int> result;

queue<int> q;

q.push(root);

while(q.size()>0){

int curr = q.front();

q.pop();

visited.insert(curr);

result.push_back(curr);

for(int i: map[curr]){

if(visited.count(i)>0){

continue;

}

q.push(i);

}

}

return result;

}

};

# 2024. Maximize the Confusion of an Exam

A teacher is writing a test with `n`

true/false questions, with `'T'`

denoting true and `'F'`

denoting false. He wants to confuse the students by **maximizing** the number of **consecutive** questions with the **same** answer (multiple trues or multiple falses in a row).

You are given a string `answerKey`

, where `answerKey[i]`

is the original answer to the `ith`

question. In addition, you are given an integer `k`

, the maximum number of times you may perform the following operation:

- Change the answer key for any question to
`'T'`

or`'F'`

(i.e., set`answerKey[i]`

to`'T'`

or`'F'`

).

Return *the **maximum** number of consecutive* `'T'`

s or `'F'`

s *in the answer key after performing the operation at most* `k`

*times*.

**Example 1:**

`Input: answerKey = "TTFF", k = 2`

Output: 4

Explanation: We can replace both the 'F's with 'T's to make answerKey = "TTTT".

There are four consecutive 'T's.

**Example 2:**

`Input: answerKey = "TFFT", k = 1`

Output: 3

Explanation: We can replace the first 'T' with an 'F' to make answerKey = "FFFT".

Alternatively, we can replace the second 'T' with an 'F' to make answerKey = "TFFF".

In both cases, there are three consecutive 'F's.

**Example 3:**

`Input: answerKey = "TTFTTFTT", k = 1`

Output: 5

Explanation: We can replace the first 'F' to make answerKey = "TTTTTFTT"

Alternatively, we can replace the second 'F' to make answerKey = "TTFTTTTT".

In both cases, there are five consecutive 'T's.

`class Solution {`

public int maxConsecutiveAnswers(String answerKey, int k) {

int maxSize = k;

Map<Character, Integer> count = new HashMap<>();

for(int i=0; i<k; i++){

char currCar = answerKey.charAt(i);

count.put(currCar, count.getOrDefault(currCar, 0)+1);

}

int left = 0;

for(int right=k; right<answerKey.length(); right++){

// add right char

char currCar = answerKey.charAt(right);

count.put(currCar, count.getOrDefault(currCar, 0)+1);

while(Math.min(count.getOrDefault('T', 0), count.getOrDefault('F', 0)) > k){

// remove left char

count.put(answerKey.charAt(left), count.get(answerKey.charAt(left)) - 1);

left++;

}

maxSize = Math.max(maxSize, right-left+1); // get count from left to right

}

return maxSize;

}

}

# 485. Max Consecutive Ones

Given a binary array `nums`

, return *the maximum number of consecutive *`1`

*'s in the array*.

**Example 1:**

`Input: nums = [1,1,0,1,1,1]`

Output: 3

Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

**Example 2:**

`Input: nums = [1,0,1,1,0,1]`

Output: 2

**Constraints:**

`1 <= nums.length <= 105`

`nums[i]`

is either`0`

or`1`

.

`class Solution {`

public int findMaxConsecutiveOnes(int[] nums) {

int max = 0;

int count = 0;

for(int i=0; i<nums.length; i++){

if(i==0){

if(nums[i]==1){

max=1;

count=1;

}

} else if (nums[i]==1 && nums[i-1]==1){

count++;

} else if (nums[i]==1){

count=1;

}

max=Math.max(count, max);

}

return max;

}

}

# 487. Max Consecutive Ones II

Given a binary array `nums`

, return *the maximum number of consecutive *`1`

*'s in the array if you can flip at most one* `0`

.

**Example 1:**

`Input: nums = [1,0,1,1,0]`

Output: 4

Explanation:

- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.

- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.

The max number of consecutive ones is 4.

**Example 2:**

`Input: nums = [1,0,1,1,0,1]`

Output: 4

Explanation:

- If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.

- If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones.

The max number of consecutive ones is 4.

**Constraints:**

`1 <= nums.length <= 105`

`nums[i]`

is either`0`

or`1`

.

`class Solution {`

public int findMaxConsecutiveOnes(int[] nums) {

int[] left = new int[nums.length]; // num of 1s to the left excluding itself

for(int i=1; i<nums.length; i++){

if(nums[i-1]==1){

left[i] = left[i-1]+1;

}

}

int[] right = new int[nums.length]; // num of 1s to the right excluding itself

for(int i=nums.length-2; i>=0; i--){

if(nums[i+1]==1){

right[i] = right[i+1]+1;

}

}

int max = 0;

for(int i=0; i<nums.length; i++){

max=Math.max(max, left[i]+right[i]);

}

return max+1; // 1 represents i (nums[i] can be 0 or 1)

}

}

**Follow up:** What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?

**Do the sliding window approach**

`class Solution {`

public int findMaxConsecutiveOnes(int[] nums) {

int longestSequence = 0;

int left = 0;

int right = 0;

int numZeroes = 0;

// while our window is in bounds

while (right < nums.length) {

// add the right most element into our window

if (nums[right] == 0) {

numZeroes++;

}

// if our window is invalid, contract our window

while (numZeroes == 2) {

if (nums[left] == 0) {

numZeroes--;

}

left++;

}

// update our longest sequence answer

longestSequence = Math.max(longestSequence, right - left + 1);

// expand our window

right++;

}

return longestSequence;

}

}

# 1004. Max Consecutive Ones III

Given a binary array `nums`

and an integer `k`

, return *the maximum number of consecutive *`1`

*'s in the array if you can flip at most* `k`

`0`

's.

**Example 1:**

`Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2`

Output: 6

Explanation: [1,1,1,0,0,1,1,1,1,1,1]

Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

**Example 2:**

`Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3`

Output: 10

Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]

Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

**Constraints:**

`1 <= nums.length <= 105`

`nums[i]`

is either`0`

or`1`

.`0 <= k <= nums.length`

**Similar to 2024**

`class Solution {`

public int longestOnes(int[] nums, int k) {

int maxSize = k;

Map<Integer, Integer> count = new HashMap<>();

for(int i=0; i<k; i++){

int currCar = nums[i];

count.put(currCar, count.getOrDefault(currCar, 0)+1);

}

int left = 0;

for(int right=k; right<nums.length; right++){

// add right char

int currCar = nums[right];

count.put(currCar, count.getOrDefault(currCar, 0)+1);

while(count.getOrDefault(0, 0) > k){

// remove left char

count.put(nums[left], count.get(nums[left]) - 1);

left++;

}

maxSize = Math.max(maxSize, right-left+1); // get count from left to right

}

return maxSize;

}

}

# 2661. First Completely Painted Row or Column

You are given a **0-indexed** integer array `arr`

, and an `m x n`

integer **matrix** `mat`

. `arr`

and `mat`

both contain **all** the integers in the range `[1, m * n]`

.

Go through each index `i`

in `arr`

starting from index `0`

and paint the cell in `mat`

containing the integer `arr[i]`

.

Return *the smallest index* `i`

*at which either a row or a column will be completely painted in* `mat`

.

**Example 1:**

`Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]`

Output: 2

Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

**Example 2:**

`Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]`

Output: 3

Explanation: The second column becomes fully painted at arr[3].

`class Solution {`

public int firstCompleteIndex(int[] arr, int[][] mat) {

Map<Integer, int[]> map = new HashMap<>();

for(int i=0; i<mat.length; i++){

for(int j=0; j<mat[0].length; j++){

int[] coord = {i, j};

map.put(mat[i][j], coord);

}

}

Map<Integer, Integer> rows = new HashMap<>();

Map<Integer, Integer> cols = new HashMap<>();

for(int i=0; i<arr.length; i++){

int[] coord = map.get(arr[i]);

rows.put(coord[0], rows.getOrDefault(coord[0], 0)+1);

cols.put(coord[1], cols.getOrDefault(coord[1], 0)+1);

if(rows.get(coord[0]) == mat[0].length){

return i;

} else if (cols.get(coord[1]) == mat.length){

return i;

}

}

return 0;

}

// 4,3,5

// 1,2,6

}

# 2483. Minimum Penalty for a Shop

You are given the customer visit log of a shop represented by a **0-indexed** string `customers`

consisting only of characters `'N'`

and `'Y'`

:

- if the
`ith`

character is`'Y'`

, it means that customers come at the`ith`

hour - whereas
`'N'`

indicates that no customers come at the`ith`

hour.

If the shop closes at the `jth`

hour (`0 <= j <= n`

), the **penalty** is calculated as follows:

- For every hour when the shop is open and no customers come, the penalty increases by
`1`

. - For every hour when the shop is closed and customers come, the penalty increases by
`1`

.

Return* the **earliest** hour at which the shop must be closed to incur a **minimum** penalty.*

**Note** that if a shop closes at the `jth`

hour, it means the shop is closed at the hour `j`

.

**Example 1:**

`Input: customers = "YYNY"`

Output: 2

Explanation:

- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.

- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.

- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.

- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.

- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.

Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.

**Example 2:**

`Input: customers = "NNNNN"`

Output: 0

Explanation: It is best to close the shop at the 0th hour as no customers arrive.

**Example 3:**

`Input: customers = "YYYY"`

Output: 4

Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.

**Constraints:**

`1 <= customers.length <= 105`

`customers`

consists only of characters`'Y'`

and`'N'`

.

`class Solution {`

public int bestClosingTime(String customers) {

int currPenalty = 0;

for(int i=0; i<customers.length(); i++){

if(customers.charAt(i) == 'Y'){

currPenalty++;

}

}

int minPenalty = currPenalty; // penalty when shop never open at all

int earliestHour = 0;

for(int i=0; i<customers.length(); i++){

char ch = customers.charAt(i);

if(ch == 'Y'){

currPenalty--; // shop open and cus entered shop, so no penalty

} else {

currPenalty++; // shop open but no cus, so penalty

}

if(currPenalty < minPenalty){

earliestHour = i+1;

minPenalty = currPenalty;

}

}

return earliestHour;

}

}

Let nn*n* be the length of `customers`

.

Time complexity: O(n)

- The first traversal is used to calculate the total count of ‘Y’ in
`customers`

, which takes O(n) time. - In each step of the second traversal, we update
`cur_penalty`

,`min_penalty`

, and`earliest_hour`

based on the character`customers[i]`

, which can be done in constant time. Therefore, the second traversal also takes O(n) time.

Space complexity: O(1)

- We only need to update several parameters,
`cur_penalty`

,`min_penalty`

and`earliest_hour`

, which takes O(1) space.

**Alternative**

`class Solution {`

public int bestClosingTime(String customers) {

// Start with closing at hour 0 and assume the current penalty is 0.

int minPenalty = 0, curPenalty = 0;

int earliestHour = 0;

for (int i = 0; i < customers.length(); i++) {

char ch = customers.charAt(i);

// If status in hour i is 'Y', moving it to open hours decrement

// penalty by 1. Otherwise, moving 'N' to open hours increment

// penalty by 1.

if (ch == 'Y') {

curPenalty--;

} else {

curPenalty++;

}

// Update earliestHour if a smaller penatly is encountered.

if (curPenalty < minPenalty) {

earliestHour = i + 1;

minPenalty = curPenalty;

}

}

return earliestHour;

}

}

# 385. Mini Parser

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return *the deserialized* `NestedInteger`

.

Each element is either an integer or a list whose elements may also be integers or other lists.

**Example 1:**

`Input: s = "324"`

Output: 324

Explanation: You should return a NestedInteger object which contains a single integer 324.

**Example 2:**

`Input: s = "[123,[456,[789]]]"`

Output: [123,[456,[789]]]

Explanation: Return a NestedInteger object containing a nested list with 2 elements:

1. An integer containing value 123.

2. A nested list containing two elements:

i. An integer containing value 456.

ii. A nested list with one element:

a. An integer containing value 789

`/**`

* // This is the interface that allows for creating nested lists.

* // You should not implement it, or speculate about its implementation

* public interface NestedInteger {

* // Constructor initializes an empty nested list.

* public NestedInteger();

*

* // Constructor initializes a single integer.

* public NestedInteger(int value);

*

* // @return true if this NestedInteger holds a single integer, rather than a nested list.

* public boolean isInteger();

*

* // @return the single integer that this NestedInteger holds, if it holds a single integer

* // Return null if this NestedInteger holds a nested list

* public Integer getInteger();

*

* // Set this NestedInteger to hold a single integer.

* public void setInteger(int value);

*

* // Set this NestedInteger to hold a nested list and adds a nested integer to it.

* public void add(NestedInteger ni);

*

* // @return the nested list that this NestedInteger holds, if it holds a nested list

* // Return empty list if this NestedInteger holds a single integer

* public List<NestedInteger> getList();

* }

*/

class Solution {

public NestedInteger deserialize(String s) {

if(s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));

Stack<NestedInteger> stack = new Stack<>();

int start = 1;

for(int i=0; i<s.length(); i++){

char c = s.charAt(i);

if(c == '['){

stack.push(new NestedInteger()); // start of a new obj

start = i+1; // next position is the start of the new number

} else if (c == ','){

NestedInteger parent = stack.peek();

if(start<i){

parent.add(new NestedInteger(Integer.valueOf(s.substring(start, i))));

}

start = i+1;

} else if (c==']'){

NestedInteger top = stack.pop();

if(start<i){

top.add(new NestedInteger(Integer.valueOf(s.substring(start, i))));

}

start = i+1;

if(!stack.isEmpty()) stack.peek().add(top);

else return top;

}

}

return null;

}

}