Revelations

Question 1

Using TreeMap + DP

TreeMap can be used to store in sorted order.

You can do the sorting based on values too and then get ur keys, as how there positions changed. after sorting. (The one you try to do always, sort something based on other.)

We can get next big and next small keys in O(logn).

Answer 1

As we used in the problem of Odd-Even Jumps in an array to reach the end Index of an array.

Question 2

Using Stacks with a class.

Like used In the problem of Sum of Subarray Minimums,
We can use a stack with a custom class like value & count.

Very smart usage of stacks in this problem.

Answer 2

https://leetcode.com/problems/sum-of-subarray-minimums/solution/

Question 3

Subarray Problems.

Examples:
1. Longest contiguous subarray with a sum greater than 0. (https://leetcode.com/problems/longest-well-performing-interval/)

2. Count of contiguous subarrays with a sum equal to k.
3. Longest contiguous subarray with a sum equal to k.

(https://leetcode.com/problems/contiguous-array/)

Answer 3

1. Prefix/Cumulative Sum, store only the left-most occurrence in the idxMap since there can be duplicates and we want the longest.
2. HashMap to store prefixes occurrences count or index where it occurred or relevant info according to the problem.

Most Cases:

if the longest subarray is asked, we maintain indexes of prefixes in hashmap values, to calculate the max length.

if the count of subarrays is asked, we maintain a count of the prefix occurrences in hashmap values.

Handle duplicates of prefixes based on the problem.

Question 4

Next Greater elements

Answer 4

Standard Stack.

1. Keep adding small numbers to stack.
2. When a bigger number comes, pop all the smaller ones. And this bigger no. would be the answer(nge) for all the popped elements.

Question 5

Modulo of negative numbers.
For negative numbers, the modulo % operator, will return negative.
To counter it you can use this:

int mod = num%k+k for -ve numbers we have to add k again.

(num%k+k)%k; –>works for any number +ve or -ve.

https://leetcode.com/problems/check-if-array-pairs-are-divisible-by-k/

Check If Array Pairs Are Divisible by k

Given an array of integers arr of even length n and an integer k.

We want to divide the array into exactly n / 2 pairs such that the sum of each pair is divisible by k.

Return True If you can find a way to do that or False otherwise.

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5

Output: true

Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Answer 5

public boolean canArrange(int[] arr, int k) {
int[] valIdx = new int[k];
boolean res= true;
for(int i=0;i< arr.length;i++){
int rem = arr[i]%k;
if(rem<0)rem+=k;
valIdx[rem]++;
}
if(valIdx[0]%2!=0) return false;
for(int i = 1; i < = k/2; i++){
if(valIdx[i] != valIdx[k-i]) return false;
}
return res;
}