Algorithms

neetcode 250

Concatenation of Array

Two loops: Twice (range(2) go through for num in nums and add to an array.

Contains Duplicate

Add all elements into an set then compare original to set if set smaller then return true

Valid Anagram

Speed up: if they aren’t equal length quickly return False. Make a array add 1 for letter (index num is letter ascii) in first word then subtract 1 in second. If its the same amounts it will be 0 otherwise it will be either negative or positive. iterate through array to check.

Two sum

Make a hashmap. iterate enumeration. Map number to its index. find the difference between target and itself. see if that number(the difference) is already in the map. Return their indexes (diff will be in map).

Longest Common Prefix

Two loops: (range) Iterate through the first string and (iterate) compare to all strings first make sure first isn’t longer then if that i is equal to first’s i. if not equal return result immediately. In main loop add letter to result because we dont want it duplicating for each correct letter there will be many.

Group Anagrams

Make a result map of lists and for every string make a count array (creating an array of the words letters). (like valid anagram), Turn count into a tuple and append it. return values() not keys.

Remove Element

Two Pointers: one, i, is going through length. if it isnt target make other pointer , k, (index) i, only increment k if not it return k

Majority Element

Iterate through nums. Use hash map to count each number. We want find max.

Design Hashset

Create ListNode class it gets key set that and set next to None. Initilize a set filled with 10,000, 0 list nodes (all not just first so loop). cur = self.set[key % len(self.set)] . go through linked list if next.key ever equals key we dont need to add again return immediately. Outside loop we make next key turning it into listnode. Copy paste for remove and contains. but if equal set to next next skip it.

Design Hashmap

like hashset but set key val and next in the parameters area (-1, -1, None) then itself. for put we need to put next.val == value. for get return it or -1

Merge Sort

Base Case: if l == r return array. Find middle. call itself on left to middle then middle to right but add one to middle so we dont do it again. Then merge function. Make left and right arrays. (remember right not inclusive) (I = L starts there and other pointers just zero because their going through mini arrays not arr itself)

Sort Colors

Two Pointers: make a swap function. put one number on left and one number on the right. Don’t increment i on right because we need to check the value we switched with for left we will have checked it already. if middle increment I (else).

Top K Frequent Elements

Make a count hashmap (majority element) then we want to have another loop through key and value make 2d array len(num) + 1 But not (n to c but count to number) Loop backwards to zero (just len(nums) bc were going to zero not -1). Maximum count could be the length of it so start there. Loop through every number in that specific count in freq[I] array. append it until res length is k.

Encode and Decode Strings

Put the strings into one big string but we want to put length + # then string. to decode result is an array 2 while loops first for I pointer (while I < length) set j equal to i. second loop: stop incrementing j at # so we can get length of the word. s[j + 1 : j + 1 + length] is the word put that in result and set i to j + 1 + length (not inclusive).

Range Sum Query 2D Immutable

init: Basic matrix problem make own matrix make sure plus 1 for extra border so no edge cases with the edge parts. set prefix to 0 before column loop. We add everything together into prefix. we get above c + 1. We set my matrix to border to prefix + above. sumRegion() Add 1 to params. get bottomright (mymatrix). Get top left subtract 1 (this part makes sense but above we need col2 and left we need row2). return bottomRight - above - left + topLeft

Products of Array Except Self

Prefix Sums: fill res with 1s. set prefix/posfix to 1. res[I] = prefix. now we go backwards to -1 postfix. Multiply both because already there. (multiply nums into pre/post)

Valid Sudoku

Basic 2d problem but only need to iterate 9 times for both. Make hashmap sets for cols, rows and squares. Base cases: ‘.’ continue (nothing to add) then if already in the sets. (for squares r//3 , c //3 as r or c (map key))

Longest Consecutive Sequence

turn nums into a set. while iterating over nums check if n - 1 in numset if not we reset length. while loop length += 1 while n + length is in numset (getting larger checking if n + 1 n + 2 … have). get max after while loop done.

Best Time to Buy and Sell Stock II

Skip first day. Check if today greater than yesterday then we subtract today from yesterday and add that to profits. (because we sold it yesterday and made that money)

Majority Element II

Boyer-Moore Voting Algorithm Majority Element (make count map). If count is less than or equal to 2 we continue. If not we make a new_count because we will be changing count while iterating over it. For key and value. if count is greater than 1. subtract it so only the biggest stay in the map. (dont forget to make new map old one) Finally use another loop num in count ( we only want keys) nums.count(num) is greater than length // 3 put it in result.

Subarray Sum Equals K

Prefix Sums. Just (two sum) but initialize map with {0:1} and we need a cursum adding to every iteration. and cursum - target instead of other way. and we add the diff (key) map val to result. the key is cursum and we add 1 each time.

First Missing Positive

The idea is to use the sign of each element as a flag index is the number we are looking for. 3 loops 1. turn negatives into zeros 2. mark index of the number - 1 (bc 0) as positive or negative (exists) make sure val abs exists between 1 and len 3. check if it's positive or zero if so return it bc not there skip 1 bc (I-1) to check for if not found return len(nums) + 1

Reverse String

Recursion: pass in 0, len(s) - 1 (not loop) if l < r swap l and r on same line bc python then call itself moving up and down

Valid Palindrome

Need extra function to check if its between a-z or 0-9 use ord dont forget upper case) Basic 2 pointers: but inside 2 loops while it isnt function (dont forget r > l and other way have to check inside too since another loops) After check if equal false (dont forget lower() case check and too increment/decrement)

Valid Palindrome II

basic 2 pointers: if not equal try skip the character on the left or skip the character to the right return if one is equal to itself reversed (or), skipL, skipR = s[l + 1:r + 1], s[l:r]

Merge Strings Alternately

set two pointers to zero. while loop to make sure both pointers are in range of their words. Append letter one at a time. We have to append the rest for each [like this word1[I:]] (like merge sort) return "".join(res) at end because it is not a string but a array

Merge Sorted Array

Get the last from given this will be the pointer for the main one num1 we will decrement every time no matter which one greater. While loop to check if both pointers are staying above 0. when using them subtract 1 (for 0 ie nums1[m - 1]). nums1[last] is assigned whatever wins. (like merge sort need to again for n not m dont forget decrement last)

Remove Duplicates From Sorted Array

set left = 1. right will be start at 1 right too bc we are going to check if r - 1 and r are equal. If so we swap with left (like remove element) only increment left then. return left.

Two Integer Sum II

(good thing this is sorted low key binary search) basic 2 pointer: add left and right and if that is target return it + 1 because pointers same. if smaller increase left bigger decrease right.

3Sum

Sort so we can do a binary sortish thing. We want to loop through enumerated nums. if n is greater than 0 we need to break were only looking for negative numbers. we make sure I is greater than one because we are going to check last num if its a duplicate (using enum i). If so we continue ignore duplicates. After that its just (two sum II for zero) but more than one answer so result is arr append to it (include n) for else we need to make sure l skips duplicates using while loop (also like any inner while loop make sure doesnt surpass outer)

4Sum

Recursion (kind of backtracking with/without): if k not 2 because once we get there we will just do 3sum iterate from (start, len(nums) - k + 1) make sure i is greater than start because same duplicate like 3sum. Then backtracking append to quad then call ksum target should be - nums[I] because were using it. and pop (dont forget return keyword inside if) pass in k start and target.

Rotate Array

Two Pointers: Make k = k % len(nums) then create a function inside swap left and right in the array basic two pointers way. Call three times first basic two pointers then 0 to k-1 then k to end.

Container With Most Water

Basic 2 pointers: create area (l * w) width we want the minimum of left or right because that’s where the water will flow. Res will be area find max. then binary sort ish thing again.

Boats to Save People

sort array. Need boats var. Almost basic two pointers but (<=) Need a remain variable inside loop which is limit minus biggest person right (bc we sorted) (greedyish thing) decrement right and add a boat. before we increment left we want to make sure they can fit in the boat make sure remain is >= smallest person (left) (if statement and make sure not going over while bc inside it)

Trapping Rain Water

edge case: return zero if not height (empty), Basic Two pointers: need maxL and maxR and set to initial left and right height. then (binary sort ish thing) if left smaller than right increment it update max if necessary and maxL - height[left] should be added to result. same things for if right smaller than left (but decrement)

Contains Duplicate II

make window a set. set left = 0 and r instead of I iterate through array. if r-l (length) greater than target. remove left from window and increment l (we sliding) if right already in window return true bc we saw it before (were done). after we add (keep going). (dont forget return false

Best Time to Buy and Sell Stock

set left to 0 and right to 1 make while loop while r is in range. if left is less than right profit is right minus left price. update res with profits if necessary (max) else we set left equal to right (because left should not be more so then it should be right). Increment right no matter what.

Longest Substring Without Repeating Characters

Like contains duplicate but while statement so set r to zero with left. and one while statement inside not if statements. check if r is in the set. if so remove left and increment it. outside add r to set + increment it, update res to find max length (dont forget to add 1)

Longest Repeating Character Replacement