Neetcode 150 simplifed

Contains Duplicate

Iterate through nums, adding each value to a set; if you ever see a value that's already in the set, return True - otherwise False after the loop. O(n) time, O(n) space.

Valid Anagram

Count each character with an array or dict while iterating over both strings; they're anagrams iff all counts net to zero. O(n) time, O(1) extra space if using fixed‑size array.

Two Sum

Keep a hash map from value→index; for each num x at index i, check if target‑x is already in the map. Insert x afterward. O(n) time, O(n) space.

Group Anagrams

For every word build a canonical key (sorted letters or 26‑char frequency tuple) and append the word to a hash‑map bucket keyed by that signature. O(n·k log k) with sorting, O(n·k) with tuple key.

Top K Frequent Elements

Count frequencies with a dict, then either bucket‑sort by frequency or push (−freq,val) into a min‑heap of size k. Both run in O(n) time on average.

Product of Array Except Self

Build prefix products left→right and suffix products right→left in two passes; result[i]=prefix[i‑1]*suffix[i+1]. O(n) time, O(1) extra space beyond output.

Valid Sudoku

Use three sets of 9 boolean arrays (rows, cols, 3×3 boxes); while scanning each cell ensure the digit hasn't appeared before in its row, col, or box. O(81) time, O(1) space.

Encode And Decode Strings

To encode list[str], write len(s)+'#'+s for each string; to decode, read length up to '#', slice that many chars. Handles any UTF‑8 chars and '#'.

Longest Consecutive Sequence

Insert all nums into a set; for each num that has no predecessor (num‑1 not in set) walk forward counting length until num+k not in set, tracking max. O(n) time/O(n) space.

Valid Palindrome

Two pointers from both ends skipping non‑alphanumerics; compare lowercase chars until they cross. O(n)/O(1).

Two Sum II Input Array Is Sorted

Two pointers (lo,hi) traverse sorted array adjusting toward target; O(n) time, O(1) space.

3Sum

Sort nums; fix index i and run two‑pointer search on the rest to find complements of −nums[i], skipping duplicates. O(n²).

Container With Most Water

Two pointers at ends; compute area and move pointer at shorter wall inward to seek larger area. O(n).

Trapping Rain Water

Two‑pointer scan keeping leftMax/rightMax; at each step add trapped = max(0,min(lMax,rMax)-height[i]). O(n).

Best Time to Buy And Sell Stock

Track min price so far and current profit = price - minPrice; update maxProfit each day. O(n).

Longest Substring Without Repeating Characters

Sliding window with dict char→latest index; shrink window when duplicate seen; track max length. O(n).

Longest Repeating Character Replacement

Window counts plus maxFreq; shrink while window‑maxFreq>k; record longest. O(n).

Permutation In String

Sliding window length |p| with char frequency arrays; window matches pattern when counts equal. O(n).

Minimum Window Substring

Expand window until it contains all chars of t, then shrink from left while maintaining requirement; keep shortest window. O(n).

Sliding Window Maximum

Monotonic deque of indices with decreasing values; front is maximum of current window. O(n).

Valid Parentheses

Stack of opening brackets; pop and check type on closing bracket; valid if stack empty at end. O(n).

Min Stack

Maintain auxiliary stack of current mins paralleling push/pop operations; min is top of aux stack. O(1).

Evaluate Reverse Polish Notation

Stack operands; on operator pop two, apply, push result; final element is answer. O(n).

Generate Parentheses

Backtrack keeping counts of open/close used; append to result when open==close==n.

Daily Temperatures

Monotonic stack of indices; for each day, pop while temp higher and compute wait; push index. O(n).

Car Fleet

Sort cars by position descending, compute time = (target‑pos)/speed; count fleet when time > lastTime seen. O(n log n) sort + O(n).

Largest Rectangle In Histogram

Scan bars with increasing stack; compute area when current bar lower than stack top, using popped height and width. O(n).

monotonic stack

Binary Search

Iteratively halve search range on sorted array until target found or bounds cross. O(log n).

Search a 2D Matrix

Binary search treating matrix as flattened sorted list; map mid back to row/col. O(log mn).

Koko Eating Bananas

Binary search speed 1..maxPile; total hours=Σ⌈pile/speed⌉; pick smallest speed meeting H. O(n log maxPile).

Search In Rotated Sorted Array

Binary search while checking which half is sorted to discard wrong half. O(log n).

Find Minimum In Rotated Sorted Array

Binary search for pivot where array values decrease; min is at pivot. O(log n).

Time Based Key Value Store

Dict key→list[(ts,val)]; set appends; get uses bisect to find latest ts ≤ query. O(log m).

Median of Two Sorted Arrays

Binary search partition of shorter array such that left parts size equal and maxLeft ≤ minRight; derive median. O(log min(m,n)).

Reverse Linked List

Iterative pointer reversal with prev, cur, next; return prev at end. O(n).

Merge Two Sorted Lists

Iteratively build new list taking smaller head from l1 or l2 each step. O(m+n).

Reorder List

1) find mid, 2) reverse second half, 3) merge nodes alternately from start and reversed half.

Remove Nth Node From End of List

Advance fast n nodes then move slow & fast until fast.next=None; delete slow.next.

Copy List With Random Pointer

Clone nodes interleaved, set random via original.random.next, then separate lists. O(n)/O(1).

Add Two Numbers

Traverse both lists adding digits and carry; create new nodes; after loop add carry if any. O(max(m,n)).

Linked List Cycle

Floyd's tortoise and hare: fast moves 2, slow moves 1; meet implies cycle.

Find The Duplicate Number

Floyd's cycle detection on index graph nums[i]; entrance is duplicate.

LRU Cache

Hash map key→node plus doubly‑linked list; on access move node to head; on insert evict tail when size exceeds cap.

Merge K Sorted Lists

Min‑heap of current heads; pop min, push its next; build merged list. O(N log k).

Reverse Nodes In K Group

Iteratively reverse sublists of length k using pointer manipulation; leave remainder

Invert Binary Tree

Recursively swap left/right child of each node.

Maximum Depth of Binary Tree

Post‑order DFS returning 1+max(leftDepth,rightDepth).

Diameter of Binary Tree

DFS returning height; update global best with left+right heights each node.

Balanced Binary Tree

DFS returning height if balanced else ‑1 early exit.

Same Tree

DFS comparing val, left subtree, right subtree for equality.

Subtree of Another Tree

DFS through main tree calling isSame at each node until match found.

Lowest Common Ancestor of a Binary Search Tree

Iterate from root; move to child side where both p and q lie until diverge.

Binary Tree Level Order Traversal

Queue BFS collecting node values by level.

Binary Tree Right Side View

BFS saving last node per level or DFS right‑first capturing first visit depth.

Count Good Nodes In Binary Tree

DFS passing pathMax; node is good if val≥pathMax; recurse updating max.

Validate Binary Search Tree

In‑order traversal ensuring current val > previous val.

Kth Smallest Element In a Bst

In‑order traversal decrement k until zero then return node value.

Construct Binary Tree From Preorder And Inorder Traversal

Use preorder index to pick root; split inorder into left/right; recurse; store inorder value→index for O(1) splits.

Binary Tree Maximum Path Sum

DFS returns max downward path; update global with left+right+node.

Serialize And Deserialize Binary Tree

Preorder serialization with '#' for nulls; deserialize by reading tokens recursively.

Implement Trie Prefix Tree

Each node stores children dict and end flag; insert/search/prefix all straightforward.

Design Add And Search Words Data Structure

Trie search supports '.' wildcard by DFS exploring all children when char=='.'.

Word Search II

Insert words into trie; DFS backtracking on board pruning dead paths; mark found words to avoid duplicates.

Kth Largest Element In a Stream

Keep min‑heap of size k; push val, pop when size>k; kth largest is heap[0].

Last Stone Weight

Max‑heap stones; repeatedly smash top two; push diff if non‑zero; return remaining or 0.

K Closest Points to Origin

Max‑heap size k storing (dist,point); push and pop if size>k; return stored points.

Kth Largest Element In An Array

Quickselect partition average O(n) or min‑heap size k for O(n log k).

Task Scheduler

Greedy formula: idleSlots=(maxFreq‑1)*(n+1‑r) minus tasks counts; answer=max(len(tasks),len(tasks)+idleSlots).

Design Twitter

Hash maps for follow relationships and per‑user tweet list; news feed merges recent tweets with max‑heap of (time,tweetId).

Find Median From Data Stream

Two heaps - max‑heap lower half, min‑heap upper; rebalance sizes; median is avg of roots or root of bigger heap.

Subsets

Backtracking building path or bitmask enumeration for all 2^n subsets.

Combination Sum

DFS choosing candidate >= current index, passing remaining target; backtrack when remainder negative.

Permutations

Backtrack swapping current index with each idx≥current; restore order on return.

Subsets II

Sort nums; backtrack skipping duplicates when choosing next element.

Combination Sum II

Sort nums; backtrack, at each depth skip duplicates; each element used at most once.

Word Search

DFS backtracking on grid matching word letters with visited set; prune on mismatch.

Palindrome Partitioning

Backtrack choosing palindrome prefixes; recurse on suffix; gather partitions.

Letter Combinations of a Phone Number

Backtracking appending letters for each digit until length==digits length.

N Queens

Backtrack rows using sets for cols and diagonals; construct board on success.

Number of Islands

DFS/BFS marking visited land cells to count connected components.

Clone Graph

DFS/BFS cloning nodes with hashmap mapping original→clone.

Max Area of Island

DFS flood fill counting area; track maximum.

Pacific Atlantic Water Flow

BFS/DFS from Pacific and Atlantic edges separately; cells reachable by both in intersection.

Surrounded Regions

DFS from border 'O's marking safe; flip remaining 'O's to 'X'.

Rotting Oranges

Multi‑source BFS from initial rotten cells; minutes equals levels; return -1 if fresh remains.

Walls And Gates

Multi‑source BFS from gate cells, writing steps to each empty room.

Course Schedule

Topological sort via indegree queue; detect cycle by processed count.

Course Schedule II

Same as above but append nodes to ordering vector as they're processed.

Redundant Connection

Union‑Find; first edge connecting vertices already in same set is redundant.

Number of Connected Components In An Undirected Graph

Union‑Find merging edges; initially n sets; answer is number of roots.

Graph Valid Tree

Graph with n nodes is tree if connected and edges==n‑1; use union‑find or DFS to test.

Word Ladder

BFS using intermediate wildcard mapping for neighbor generation; return level when end reached.

Reconstruct Itinerary

Hierholzer's algorithm with min‑heap adjacency lists; postorder DFS and reverse result.

Min Cost to Connect All Points

Prim's MST using min‑heap of (dist, node); pushed edges from current MST frontier.

Network Delay Time

Dijkstra using adjacency list; answer is max distance if all nodes reachable else -1.

Swim In Rising Water

Dijkstra on grid where edge weight is max(currentHeight,nextHeight); min time to reach end.

Alien Dictionary

Build precedence graph by comparing consecutive words; Kahn topological sort; detect cycle.

Cheapest Flights Within K Stops

Use BFS/Dijkstra with (node, stops) state, or Bellman‑Ford K+1 iterations; track min cost within K stops.

Climbing Stairs

Fib DP with two variables updated iteratively.

Min Cost Climbing Stairs

DP from bottom: cost[i]+=min(cost[i+1],cost[i+2]); or forward DP.