Tags/Topics

arrays, sorting, two-pointers, sliding-window, hashing, hash-table, kadens, cyclic-sort

🧬 → Algorithm Problem
💎 → Gem

Basic Concepts

• Imp Code Snippets/Logics
• Java Cheat Sheet Notion Link ↗
• Var Args - Java
• Loops & Conditions
• Strings & StringBuilder - Java
• Boxing, Unboxing, Auto-boxing - Java
• Patterns
• Second Largest Element

Popular Algorithms

Algorithm	Description
🧬 💎 Find the Duplicate Number - Floyd's Cycle Detection Algo - Tortoise & Hare
Linear Search Algorithm + Recursion Version LS
Binary Search Algorithm + Order-Agnostic BS
Bubble Sort Algorithm	Compare every two adjacent elements and swap them if the first is > than second element. Largest element will be kept at the end after each pass
Selection Sort Algorithm	Pick the ith smallest element in each iteration and put it at correct index. Idea is to find the min/max element in an unsorted array and then put it at correct position
Insertion Sort Algorithm
Merge Sort - Two Way Iterative Approach
How to merge 3 lists at a time using 3-way merging approach	Merge 3 sorted lists using 3 pointers. But in general we will be using only 2-way merging method to merge n lists. let's suppose n is 3. first merge the lists A,B and then merge C with A,B result. So in this way two lists will be merged in each step. The same approach will be used in merge sort algorithm as well
Merge Sort - Recursive Approach
HashMaps & Hashing Concept
Sieve Of Eratosthenes - Prime Numbers	Find all the primes in a given range
SQRT of a Number	Find the SQRT of a Number using Binary Search. Even if number is not a perfect square
Euclidean Algorithm - GCD of Two Nums	Find GCD of two nums. Brute force, Eculidean Algorithm (Repeated Subtraction & Repeated Division)

Arrays

Problem Details	Description
Valid Mountain Array Easy
Rotate Array Medium Two Pointers
💎 Product of Array Except Itself Medium Prefix Sum Suffix Sum
Minimum Size Subarray Sum Medium Two Pointers Sliding Window
LC 349. Intersection of Two Arrays Easy
Check If arrays is sorted & Rotated Easy
Remove Duplicates From Sorted Array Easy
💎 Move Zeroes Easy
🧬 Majority Element - Moore's Voting Algorithm Easy
💎 Number of Arithmetic Triplets Easy
💎 Remove Duplicates From Sorted Array II Medium
💎💎 442. Find all Duplicates in an Array Medium
💎 41. First Missing Positive Hard
💎 2028. Find missing observations Medium	Nice Math Problem. It's all about dividing missingRollSum into n parts. Each roll min val will be missingRollSum/n and consider quotient as well

2D Arrays

Status	Problem Details	Description
[x]	289. Game of Life Medium

Strings

Problem Details	Description
Valid Anagram Easy
796. Rotate String - Find if s can become g after some rotations Easy	BruteForce: return (s+s).contains(g). Optimal: Get the starting index (s.char(i) == g.charAt(i)) and check if the strings are equal. Use (i%len) if pointers goes out of index.
Reverse words in a String Medium
💎💎 14. Longest Common Prefix	BruteForce: find the minlen of all string and check the each char of each string until minlen. Optimal: sort the given list of strings. find the max common prefix len for first and last strings
💎 Generate All Substrings, Subsequences, Permutations of String

Binary Search

Problem Details	Description
Find Ceil & Floor of a Number
Find Smallest letter greater than target Easy	Find the ceil of a given letter in the array
Search Insert Position	Same as finding the Ceil of a given target
💎 First & Last position of element in sorted array Medium	Find the given target using normal Binary Search. once the target is found at mid, it could be the potential first or last index, but more target elements may exists before or after mid. so if we are finding the first index then set end pointer to mid - 1 or if it's last index, set start pointer to mid + 1
💎 852 Peak Index in a Mountain Array
💎 Find in Mountain Array Hard	Find the peak index first. Then apply order-agnostic binary search on both the arrays (before peak and after peak)
33. Search Element in Rotated Sorted Array	First, determine which part of the array is sorted (the part before the mid or the part after the mid using condition (nums[start] <= middle) ). Then figure out where the target lies in the left part or right part of array
81. Search Element in Rotated Sorted Array 2	Same as above problem. But one extra condition if(middle == nums[start] && middle == nums[end]) will be added since duplicate elements are there [1, 0, 1, 1, 1]. In that condition we have to move start and end pointers as long as both the values are same.
2563. Count the Number of Fair Pairs	Brute force: Use a nested for loop O(n^2) and find the pairs. Optimal: Sort the array then fix each num in array and find the lower bound and upper bound for that number using binary search. Let's say given lower=3, upper=6 and nums =[0, 1, 4, 4, 5, 7] now when num is 1 then the other number should be atleast 2 (3-1) and max pair num should be 5 (6-1)
875. Koko Eating Bananas	**Brute force:**Start with 1 banana per hour and then keep on increasing the per hour banana count by 1 until the totalHours <= h. Like a linear search - start from 1 to maxOfAllPiles. Optimal: Replace Linear Search with BS
2064. Minimized Maximum of Products Distributed to Any Store	Similar to Koko Eating Bananas Problem

Sorting

Problem	Description
3301. Maximize the Total Height of Unique Towers Medium	Hashmaps & Sorting usecase problem

Two Pointers

Problem Details	Description
167 Two Sum II - Input Array Is Sorted Medium
💎 125 Valid Pallindrome Easy
💎 680 Valid Pallindrome II Easy
💎 LC 13. 3Sum Medium
💎 88 Merge Sorted Array Medium
💎 Duplicate Zeros code	use extra array to generate the result

Sliding Window

🌻 Must solve all these sliding window problems

Problem Details	Description
209. Minimum Size Subarray Sum	Keep on calculating the sum. and check if sum >= target then decrease the windown size from left and update min length
1493. Longest Subarray of 1's After Deleting One Element	Maintain a sliding window where there is at most one zero in it. when the second zero is found the move the leftPointer to prevZeroIndex+1
1423. Maximum Points You Can Obtain from Cards	With Extra Space(prefix sum): Calculate total sum of array now maintain the subarray of len n-k and remove it's sum from total sum. Constant Window Optimal: Calculate the first k elements sum(first window) now subtract one element from left and add one element from right to that window sum.
3. Longest substring without repeating characters	Use hashmap and keep track of each char last appeared index. if the repeat is found then move the window's left pointer
1004. Max Consecutive Ones III	Keep only atmost k zeros in a window. once zeros count exceeds k. then shrink the windowLeftIndex until one zero is removed from left.
904. Fruit Into Baskets	since we can pick only 2 types of fruits, maintain a hashmap of fruti frequencies. when map size > 2 shrink the starting point(window left index) until map size becomes 2(when the freq of any fruit reaches 0 then remove it from hashmap)
Longest Substring With At Most K Distinct Characters	Same as Fruit Into Baskets problem
2461. Maximum Sum of Distinct Subarrays With Length K	Fixed window. Maintain a window of size k and keep track of distinct elements using a hashmap, if distinct elements == k then consider that subarray sum
438. Find All Anagrams in a String	Fixed window. Maintain a window of size s1.length() and slide the window over s2 string. Create two hash maps of size 26 to have the freq of chars in two strings. when hash arrays are equal then it's anagram
567. Permutation in a String	Almost same as above problem. Fixed window
424. Longest Repeating Character Replacement	get the min replacement count for each window. once replacement count > k then shrink the left window
Count No. of Subarrays Pattern Problems From Here
1358. Number of Substrings Containing All Three Characters	We need to count all the valid substrings. valid substring should contain all 3 a,b,c chars. Keep Track of last seen indexes of each char, initialize all three to -1(create an array of size[3]) when all three are valid indexes then we found the valid substring. "ababc" We found the valid substring at index 4 then the closest left index to form a valid substring is 2(char a) so that is one substring and before that we have two more chars, so 1 + 2 substrings. everytime we find valid substring then can calculate the substrings till that index in this way.
2537. Count the Number of Good Subarrays	Counting subarrays logic is similar to LC 1358 Problem
930. Binary Subarrays With Sum	Quite interesting problem. Same as 560 Subarray sum equals K but that problem uses extra space for keeping track of prefix sums. And traditional sliding window approach also doesn't work because we might miss counting few subarrays while shrinking window. Dry run [1, 0, 0, 1, 1, 0] array to see how. Optimal Solution: count(sum<=goal) - count(sum<=goal-1)
992. Subarrays with K Different Integers	Traditional slidind window approach won't work. Dry run [2, 1, 1, 1, 3, 4, 3, 1] to see why. **Optimal Solution:**Use count(sum<=goal) - count(sum<=goal-1)
2303. Count Subarrays With Score Less Than K	Same as 713. Subarray Product Less Than K
3254. Find the Power of K-Size Subarrays I	Fixed-size window problem. just keep track of a last index where consecutiveness is missed, If that index is less than or equal to leftPointer then we can say current window elements are sorted, and last element will be the score

Prefix Sum & Suffix Sum

Problem Details	Description
💎 GFG: Longest Sub-Array with Sum K (+ve and -ve)	This problem looks like a sliding window problem but it can't be solved using sliding window approach because array contains -ve & +ve numbers. So we need to use HashMap and store the prefixsum,index
💎 560. Subarray Sum Equals K	Keep track of prefix sum in each step and increase count in two conditions. **1:**When prefix sum == k then we found the subarray with sum k. **2:**Suppose the prefix is x now but we are looking for k, so if we can find subarray with x-k simply we can remove that part and remaining subarray sum will be k, so look for prefixSum - k in hashmap. Remember prefix sum can be repeated since arr contains -ve numbers and 0 also
💎💎 525. Contiguous Array	almost same as subarray sum equal K problem where we need to get the total subarrays count but here we need to find the longest subarr length. since array contains only 0 and 1 and we need to find the max subarray with equal 0's and 1's, consider 0 as -1 and 1 as 1 only, now find the prefix sum when sum == 0 then find the max len and store the prefix sum in hashmap in each step and check if 0-prefixSum already exists in hashmap.

Recursion & Backtracking

Problem Details	Description
💎💎 Recursion Concept	Fibonacci, Factorial, Sum Of Digits, Reverse a Number, Pow(x,n), Binary Search Using Recursion
💎💎 Recursion on Arrays	Reverse Array, IsArraySorted, Linear Search, Search in Rotated Sorted Array
💎💎 Find all Indexes of target in Array	A Recursive fn whole return type is List. With & without passing the list in arguments.
💎 50. Pow(x,n)	Naive Recursive approach to Recursive calls Optimized approach
Count Zeros (or any digit) in a Number	Count Zeros in a given number using recursion
Number of Steps to Reduce a Number to Zero
💎 Print Triangle Patterns using Recursion
Bubble Sort & Selection Sort Using Recursion
🌻💎 Recursion on Strings	Remove a specific char, Subsets, Subsequences, Generate all subsets of an array/string
💎 231. Is Power of 2 Easy	Call the fn recursively until number becomes 1 or any other odd number. If 1 return true.
78. Subsets	Can be solved in 3 ways: Iterative Approach: Loop through given array of nums and add each num into existing subsets(Add empty subset initially), Recursive Solution: Follow processed, unprocessed approach., Bit Manipulation
1498. Number of Subsequences That Satisfy the Given Sum Condition	Brute Force: Generate all the subsequences and count the ones which satisfy the condition, But TLE. Optimal Solution: Since we don't have to return the actual subsequences but only the count, we can sort the array to find the min and max easily and use the two pointers approach to calculate the subsequences using formula 2^n
39. Combination Sum	Use typical processed/unprocessed approach but stay on the same index when a element is picked(basically left rec call - first one) since we can pick the same element any number of times. Base conditions are very important: stop when target == 0, target < 0, index == given.length.
40. Combination Sum 2	Starting from 0 we have 5 options to pick 1st element [1, 1, 1, 2, 2]. and to pick the 2nd element we will get 4 options.. so like this call fn recursively in a for loop. Pick only unique elements while picking nth element in a combination
17. Letter Combinations of a Phone Number	Check notes for explanation

Stack

Problem Details	Description
💎 Implement Stack Operations - Push, Pop, Peek, Increment(uptoIndex, incrementValue)	Implement the given stack operations in O(1) Time Complexity. Especially INC operation is bit interesting here.
2696. Minimum String Length After Removing Substrings	Pretty good problem to get started with Stack Data structure.

Heap/PriorityQueue

Problem Details	Description
2530. Maximal Score After Applying K Operations	pretty good problem to get started with Heap
451. Sort Characters By Frequency	count the freq of all chars and then push all those freq in priority queue(pq in descending order) poll each element from pq and append the char to result whose freq is equal to topFreq(polled one)

Dynamic Programming

Solved	Problem Details	Description
[ ]	💎 121. Best Time to Buy and Sell a Stock	Keep track of min price before the ith price and subtract min price from current price.

HashTable/Counting

Problem Details	Description
💎 1002. Find Common Characters Easy
202. Happy Number Easy Floyd Cycle Detection	Solution1: Store 'n' value in HashMap until (!set.contains(n)) and return true if n becomes 1. Solution2: Use Two-Pointers Fast & Slow and detect cycle using floyds cycle algo. Slow and Fast pointers will move until they become equal. return if slow == 1 or fast == 1
205. Isomorphic Strings Easy	Use HashMap and store the key value mappings, next time when key comes again in 's' then it's value should be equal to current char of 't'
2090. Word Pattern Easy	Same as Isomorphic Strings Problem
💎 2248. Intersection of Multiple Arrays Easy	Combination of Sorting and Hashing. Super Interesting Problem.
13. Roman to Integer Medium
💎 12. Integer to Roman Medium
💎 49. Group Anagrams Medium	Just one loop is enough. Sort each string and use that sorted one as key in hashmap and put the actual string as value. Anagrams will be grouped under each key
💎 128. Longest Consecutive Sequence Medium	Brute force way is to sort the array and find the longest sequence. Optimized way: Put all the elements in a HashSet and loop through the array again check if (x-1) exists in set or not. If not the x might be the starting point of longest sequence.
💎 Encode & Decode Strings Medium
Find the Length of the Longest Common Prefix Medium	SOLVED. store all the prefixes of each num in one array in hashset and iterate through another set to find the longest prefix
💎💎 1497. Check If Array Pairs Are Divisible by k	suppose k = 5, now we can say 7 and 3 is a pair whose sum is divisible by 5 by checking the modulo of 7 and 3. Sum of Mod of each number should be equal to k. 7%5 is 2 and 3%5 is 3. so 2 + 3 is 5, that's how we can find a pair.

Maths & Bit Manipulation

Problem Details	Description
✨ Bit Manipulation Basics	Find the ith Bit(set or not); Swap Two Numbers using XOR; Set the ith Bit of a Number; Clear the ith Bit; Count the set bits
💎 67. Add Binary	Add two given binary numbers using math.
Binary to Decimal
✨ Missing Number Easy
389. Find the Difference Easy
231. Is Power of 2 Easy	If a number if power of two then and between n & n-1 should be 0. If n is power of two then obviously there will be only one 1 in binary representation.
2220. Minimum Bit Flips to Convert Number Easy	we have to flip the bits if they are not same. so xor will be 1 if the two bits are different. so Integer.countBits(start ^ goal)
78. Subsets Medium	Use binary numbers as marking and pick the elements from given array when the bit in each number is 1. This can also be solved using Recursion
136. Single Number Easy	Since every number is repeated twice except one. perform xor of all the numbers. Same numbers xor results in zero
137. Single Number II Medium	Check each bit (32 bits) of all given numbers. Sum of the no. of ones at each ith bit position across all numbers should be a multiple of 3; if not, set the ith bit in the result.
XOR of numbers from L to R Easy	Start writing xor of numbers from 1 to 8 or 12, you'll observe a pattern. So based on that if we want xor of range getXorOfN(left-1) ^ getXorOfN(right); 4 to 7 means (1 to 7) ^ (1 to 3)
💎 453. Minimum Moves to Equal Array Elements	Instead of thinking abt how to increment elements to make them equal, consider how many decrements it would take to reduce all the elements equal to smallest value. Incrementing all elements except one is the same as decrementing only one element.

Cyclic Sort

Problems that can be solved using cyclic sort technique

• Find the Duplicate Number - Using Cyclic Sort
• 645. Set Mismatch
• 442. Find all Duplicates in an Array
• 448. Find All Numbers Disappeared in an Array
• 268. Missing Number
• CSES Missing Number

Bucket Sort

Problems that can be solved using Bucket sort technique

• 💎 Minimum Time Difference

CSES Problem Set

Introductory Problems: Weird Algorithm, Missing Number, Repetitions, Increasing Array, Permutations

Dynamic Programming: