Detailed Neetcode 150

Given a list of integers, return true if any value appears at least twice, else false.

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.

Given two strings s and t, determine whether t is an anagram of s.

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.

Given an array of integers nums and an integer target, return indices of the two numbers that add up to target.

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.

Given an array of strings, group the strings that are anagrams of each other.

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.

Given an integer array nums and an integer k, return the k most 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.

Given an integer array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i] (without using division).

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.

Given a 9×9 Sudoku board, determine if it is a valid Sudoku configuration.

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.

Design encode and decode functions to convert a list of strings into a single string and back, guaranteeing lossless round‑trip.

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 '#'.

Given an unsorted array of integers, return the length of the longest consecutive elements 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.

Given a string s, return true if, after ignoring non‑alphanumeric chars and case, it reads the same forwards and backwards.

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

Given a sorted integer array nums and an integer target, return the indices (1‑indexed) of the two numbers that add up to target.

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

Given an integer array nums, return all unique triplets [a,b,c] such that a + b + c = 0.

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

Given n lines of heights, find two lines that together with the x‑axis form a container containing the most water.

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

Given elevation map heights where width = 1, compute how much water it can trap after raining.

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

Given an array of stock prices, find the maximum profit from one buy-sell transaction.

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

Given a string s, find the length of the longest substring without repeating characters.

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

Given a string s and an integer k, return the length of the longest substring you can obtain after replacing at most k characters so that the substring contains only one repeating letter.

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

Given two strings s1 and s2, return true if s2 contains a permutation of s1.

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

Given strings s and t, return the minimal window in s that will contain all characters in t (including multiplicity).

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

Given an array nums and a window size k, return the maximum value in each sliding window.

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

Given a string containing brackets '()[]{}', determine if the string is valid.

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

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

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

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

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

Given n pairs of parentheses, return all combinations of well‑formed parentheses.

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

Given an array of daily temperatures, return how many days you would have to wait until a warmer temperature for each day.

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

Given target distance and starting positions and speeds of cars driving toward it, count the number of car fleets that will arrive.

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

Given histogram bar heights, return the area of the largest rectangle in the histogram.

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

Given a sorted array nums and a target, return the index of target if found, else ‑1.

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

Given an m×n matrix where each row is sorted and first element of each row is greater than last of previous row, search target.

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

Given piles of bananas and integer h, return the minimum integer speed k to eat all bananas within h hours.

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

Given a rotated sorted array nums and a target, return the index of target or ‑1.

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

Given a rotated sorted array nums, return the minimum element.

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

Design a time‑based key‑value store that supports set(key, value, timestamp) and get(key, timestamp) returning the value set for key at the largest timestamp ≤ query time.

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

Given two sorted arrays nums1 and nums2, return their median in O(log(m+n)) time.

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

Given head of a singly linked list, reverse the list and return the new head.

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

Merge two sorted linked lists into a single sorted list and return it.

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

Given head of linked list, reorder it to: L0→Ln→L1→Ln-1→... in place.

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

Remove the n‑th node from the end of a linked list and return its head.

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

Deep‑copy a linked list where each node has next and random pointers.

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

Add two non‑negative integers represented by reversed linked lists and return the sum as a linked list.

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

Given head of a linked list, determine if the linked list has a cycle.

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

Given array nums containing n+1 integers where each integer is between 1 and n inclusive, return the duplicate number.

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

Design a least‑recently‑used (LRU) cache that supports get and put in O(1) time.

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 linked lists and return one sorted list.

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

Reverse nodes of a linked list in groups of size k and return modified list.

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

Invert (mirror) a binary tree.

Recursively swap left/right child of each node.

Given a binary tree, return its maximum depth (root to deepest leaf length).

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

Given a binary tree, return the length (number of edges) of the diameter of the tree.

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

Given a binary tree, determine if it is height‑balanced.

DFS returning height if balanced else ‑1 early exit.

Given two binary trees, determine if they are the same tree.

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

Given root and subRoot of two binary trees, return true if subRoot is a subtree of root.

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

Given a binary search tree (BST) and two nodes, return their lowest common ancestor.

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

Return the level‑order traversal of a binary tree's node values.

Queue BFS collecting node values by level.

Return the list of node values visible from the right side of a binary tree.

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

Return number of good nodes in binary tree where good node is >= all previous on root‑to‑node path.

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

Determine if a binary tree is a valid binary search tree (BST).

In‑order traversal ensuring current val > previous val.

Given a BST and integer k, return the k‑th smallest element.

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

Construct binary tree from preorder and inorder traversal arrays.

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

Return the maximum path sum in a non‑empty binary tree (sum of node values).

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

Design algorithms to serialize and deserialize a binary tree.

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

Implement a trie with insert, search, and startsWith methods.

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

Design a data structure that adds words and can search a word with '.' wildcard matching any letter.

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

Given a board of letters and a list of words, return all words on the board.

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

Design a class that on add(val) and kthLargest() returns the k‑th largest element in the stream.

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

Smash rocks: each turn take two heaviest stones and smash; return weight of last stone (or 0).

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

Given points on 2D plane and integer k, return k points closest to origin.

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

Find the kth largest element in an unsorted array.

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

Given tasks represented by letters and an integer n cooling interval, return least total units of time needed to finish all tasks.

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

Design a simplified Twitter with posting, following, unfollowing, and news feed of recent tweets.

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

Maintain a data stream so that addNum and findMedian operate efficiently.

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

Given a set of unique integers, return all possible subsets (the power set).

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

Given candidates with unlimited reuse, return all unique combinations summing to target.

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

Given a list of unique integers, return all possible permutations.

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

Given a list that may contain duplicates, return all possible distinct subsets.

Sort nums; backtrack skipping duplicates when choosing next element.

Given candidates can be used at most once, return unique combinations summing to target.

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

Given a board and a word, determine if word exists in grid via adjacent letters (no reuse).

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

Partition a string into all possible lists of palindromic substrings.

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

Given digits as a string, return all possible letter combinations using telephone keypad mapping.

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

Return all distinct solutions to the n‑queens puzzle.

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

Given a grid of '1's and '0's, return the number of islands.

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

Clone an undirected graph and return the cloned graph's reference node.

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

Given grid of land and water, return area of largest island.

DFS flood fill counting area; track maximum.

Given heights matrix, return cells that can flow water to both Pacific and Atlantic oceans.

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

Capture all regions surrounded by 'X' on a board by flipping surrounded 'O's to 'X'.

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

Given grid of fresh and rotten oranges, return minutes until all oranges are rotten, or ‑1.

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

Given grid with walls, gates, and empty rooms, fill each empty room with distance to nearest gate.

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

Given number of courses and prerequisite pairs, determine if it is possible to finish all courses.

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

Return an order of courses to finish all given prerequisites or empty array if impossible.

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

Given edges that form a tree with one extra edge, return the edge that can be removed to make tree.

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

Given n nodes and undirected edges, return number of connected components.

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

Determine if given edges form a valid tree of n nodes.

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

Return shortest transformation sequence length from beginWord to endWord, altering one letter at a time using dictionary words.

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

Given flight tickets, reconstruct itinerary starting from 'JFK' and in lexical order.

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

Given points in a plane, return minimum cost to connect all points by edges with Manhattan distance.

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

Given times (u,v,w), number of nodes n, and source k, return time for all nodes to receive signal, else -1.

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

Grid heights; water rises over time; return minimum time required for swimmer to reach bottom‑right.

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

Given sorted dictionary of alien language, return character ordering of the language.

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

Given flights with prices, source, destination, and at most k stops, return cheapest price or ‑1.

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

Given n, return number of distinct ways to climb to the top if at each step you can climb 1 or 2 stairs.

Fib DP with two variables updated iteratively.

Given cost array, return minimum cost to reach top climbing 1 or 2 steps starting at step 0 or 1.

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