Arrays

Linked List

Observe general Pattern
3sum → 2sum wrapped in loop
4Sum → 3 sum wrapped in loop
KSum → k-1 sum wrapped in loop

Can recursion help?

Two Pointer

Two Approaches,
Wrap three sum problem inside another loop

Come up with generalized Solution for kSum and find res for k = 4.

First we sort the array. 
Then, we consider three variables: i, j, k.
k iterates from arr.length to 2 & i=0; j=k-1 act as two pointers for every k 
Using i j as two pointers in a sorted array, we calculate the triplet sum, 
if triplet sum < target, i++
if triplet sum > target j—

Does Two Sum problem wrapped inside a loop ring a bell?

First we sort the array. Then, just like 3 sum problem, we consider three variables: i, j, k.
k iterates from arr.length to 2 & i=0; j=k-1 act as two pointers for every k 
For triangle validity, we just need to check a+b > c  because array is sorted.
for every kth iterations, we check if elem at i , j, k can form a triangle. Then obviously [i+1, j, k],[i+2 ,j , k]... up till i < j  can form a triangle because array is sorted



O(n^3) will result in TLE.
Two questions, how to simplify checking validity for triangle?
How to efficiently check for all triplets without cubic complexity?

Can you build this up as a "3 sum problem" variation?

Math

Greedy

Steps
(i) Maintain a map and keep freq of every char in str
(ii) Iterate through all chars of order and if present in str, build a string with that char (include all repeats). Update freq of that char to 0 in the map.
(iii) iterate through the map to see freq of characters > 0 (implies these were not present in order) and append them to the result (include all repeats) 

Arrange str in terms of order and whatever is left append at end. Also consider cases when chars are repeated

Strings

HashMap

Java

Basics

Important hidden info is adjacent numbers can't be equal. So question to interviewer can be what about corner elements?
Ans- corner elements can be peak if only adjacent one is smaller. 

This confirms peak has to be present. So we can run binary search on more probable side. 

Steps.
1. Find mid
2. if mid is zero or length-1, return num[mid] or adjacent element based on requirement
2. if mid is peak return mid
3. else divide problem to side which feels more probable. move to left if nums[mid-1] > nums[mid] and vice versa. 

What can be used for log n complexity? Think in terms of climbing a hill. Will a peak element always be present?

Binary Search

Try on your own once!!
Keep a hashmap and a hashset.
when we replace a character in "s" to character in "t", we add that mapping to hashmap. we also add that assigned value to hashset.
This helps in tracking two constraints
1. hashmap ensures we always have same mapping for a particular character
2. hashset ensures we do not assign two character the same value
Look at code for further details.

We use minHeap to store high values, top of the minHeap is the lowest value among high values.
We use maxHeap to store low values, top of the maxHeap is the highest value among low values.
We keep the difference between maxHeap.size and minHeap.size minimum, it means maxHeap.size = minHeap.size + 1 when the total number of elements is an odd number, else maxHeap.size = minHeap.size.
When add new number num into our MedianFinder:
If num <= maxHeap.top() then it mean num belong to low values, add to maxHeap.
Else num belong to high values, add to minHeap.

Think bout how to have mid elements at your disposal always via a data structure (or using two copies of a data structure)

Heap

Try solving bottom up.
Only case to Increase count when previous element was common. Capture max in another variable as answer not necessarily in the last. Time O(N^2) Space O(N)
Efficient Soln:
1. Create a dp arrayList
2. Iterate input array and check at which index it can be added to using binarySearch.
3. If index < 0, newIndex = -(index+1) (index < 0 implies not currently in dp array but |index| indicates index where it should ideally be)
4. if newIndex ≥ dp.size() ⇒ add to arrayList
5. else set in arrayList at newIndex

For 1,
Design a minHeap, Add all elements, remove first k elements, return peek of minHeap
For 2,
- leverage binarySearch
- low is first elem, high is last elem
- check if mid is present in any of the rows
- find how many numbers are smaller (smallCount) than mid
- if  smallCount ≥ k : right = mid 
- if smallCount < k : left = mid

Two approaches
1. think Data Structure which can store repetitive elements with some order OR
2. Use the info that the 2d array is sorted and then try to put that to advantage

1. Map all the elements with their frequencies
2. Create new array with these frequencies
3. Sort this frequence array
4. Greedily keep removing highest frequency element only until array size reduces to atleast half

Non efficient. Transfer elements to temp 1D array and then push to new config array
Efficient: Go through old matrix and reset new mat indexes when limit achieved (look at github code)

Dont get intimidated by the rules. They are only defining what the subproblems will be in the cases of a,e,i,o,u.
For eg. if ith character is 'a', then recursively solve for only e. 
if ith character is 'i', solve for a,e,o,u
...and so on

Looks like backtracking because of word permutation. But actually a dp Problem. Can you bottom up or top down?

https://leetcode.com/problems/range-sum-query-2d-immutable/solution/

Simple O(n^2) is TLE. 2 Thought processes:
1. (more intuitive) For matrix m*n, think and cache in terms of m 1D arrays of size n. Precompute sum of elements upto that index for every row. then you can return sum of column range for every row.
2. Pre Calculate sumfromorigin for every element. Then while calculate sum just use sumfromOrigin & remove/adjust overlaps occuring. 

Novel solution
1. intuition is to keep finding the closest element to x. Binary search to find
* 2. mid and check if arr[mid] is closer or arr[mid+k] because by nature of
* 3. problem, either arr[mid] or arr[mid+k] can stay in our window if arr[mid] is
* 4. closer then we let go arr[mid+k] and bring right to mid. if arr[mid+k] is
* 5. closer then we let go arr[mid] and bring left to mid+1.
* 6. eventually, when left == right, we just return next k elements from left

find the closest element. then up till k times, alternatively keep filling element to left and element to right in that order.

Sliding Window

base case: 
1. when target achieved
2. when elements exhausted but target not achieved
choices for recursion: 
1. current element < target then either choose or not choose
2. else not choose the element

Think in terms of subset sum. Need to find if  subset exists with sum = totalsum/2

Graphs

Classic DP. Start thinking top down and  memoize OR simply do bottom up.

Base case is when elements finish or capacity exhausted. Recursion choices are whether to choose current element or not.

Kaizen

Active recall cards to brush up your DSA

Shuffle The Array →