Kadane's Algorithm
Question: Find a non-empty subarray with the largest sum
public static int BruteForce(int[] nums)
{
if (nums == null || nums.Length == 0)
{
return int.MinValue;
}
int maxSum = nums[0];
for (int i = 0; i < nums.Length; i++)
{
int curSum = 0;
for (int j = i; j < nums.Length; j++)
{
curSum += nums[j];
maxSum = Math.Max(maxSum, curSum);
}
}
return maxSum;
}
public static int Kadanes(int[] nums)
{
if (nums == null || nums.Length == 0)
{
return int.MinValue;
}
int maxSum = nums[0];
int curSum = 0;
for (int i = 0; i < nums.Length; i++)
{
curSum = Math.Max(curSum, 0);
curSum += nums[i];
maxSum = Math.Max(maxSum, curSum);
}
return maxSum;
}
public static int[] SlidingWindow(int[] nums)
{
int resultR = -1;
int resultL = -1;
if (nums == null || nums.Length == 0)
{
return new int[] { resultL, resultR };
}
int L = 0;
int curSum = 0;
int curMax = nums[0];
for (int R = 0; R < nums.Length; R++)
{
curSum += nums[R];
if (curSum < 0)
{
L = R+1;
curSum = 0;
continue;
}
if (curSum >= curMax)
{
resultL = L;
resultR = R;
}
}
return new int[] { resultL, resultR };
}
Sliding Windows Fixed:
Q: Given an array, return true if there are two elements within a window of size k that are equal.
public static bool CloseDuplicates(int[] nums, int k) {
HashSet<int> window = new HashSet<int>(); // Cur window of size <= k
int L = 0;
for (int R = 0; R < nums.Length; R++) {
if (R - L + 1 > k) {
window.Remove(nums[L]);
L++;
}
if (window.Contains(nums[R])) {
return true;
}
window.Add(nums[R]);
}
return false;
}
Sliding Windows - Variable Size
Question: Q: Find the length of the longest subarray, with the same value in each position.
public static int ShortestSubarray(int[] nums, int target) {
int L = 0, total = 0;
int length = int.MaxValue;
for (int R = 0; R < nums.Length; R++) {
total += nums[R];
while (total >= target) {
length = Math.Min(R - L + 1, length);
total -= nums[L];
L++;
}
}
if (length == int.MaxValue) {
return 0;
}
return length;
}
Two Pointers
Question: Check if an array is palindrome.
public static bool IsPalindrome(string word) {
int L = 0;
int R = word.Length-1;
while (L <= R) {
if (word[L] != word[R]) {
return false;
}
L++;
R--;
}
return true;
}
Question: Given a sorted input array, return the two indices of two elements which sums up to the target value. Assume there's exactly one solution.
public static int[] TargetSum(int[] nums, int target) {
int L = 0;
int R = nums.Length-1;
int sum;
while (L <= R) {
sum = nums[L] + nums[R];
if (sum > target) {
R--;
} else if (sum < target) {
L++;
} else {
return new int[2]{L,R};
}
}
return null;
}
Prefix Sum
Question: Given an array of values, design a data structure that can query the sum of a sub-array of the values.
public class PrefixSum {
List<int> prefix;
public PrefixSum(int[] nums) {
prefix = new();
sum = 0;
foreach (var num in nums) {
sum += num;
prefix.Add(sum);
}
}
public int RangeSum(int left, int right) {
return prefix[right] - prefix[left > 0 ? left-1 : 0];
}
}
Fast and Slow Pointers
Question: Find the middle of a linked list.
public static ListNode middleOfList(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
Question: Determine if a Linked List has a cycle.
public static bool HasCycle(ListNode head) {
HashSet<ListNode> visited = new HashSet<ListNode>();
while (head != null) {
if (visited.Contains(head)) {
return true; // Cycle found
}
visited.Add(head);
head = head.next;
}
return false; // No cycle
}
The solution above has an O(n) space complexity. Therefore, using two pointers we attempt to improve it:
public static bool hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
Question: Determine if a Linked List has a cycle and return the head.
public static ListNode cycleStart(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}
ListNode slow2 = head;
while (slow != slow2) {
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
Trie (Prefix Tree)
The goal of a trie is to insert words (string of characters) in constant time and search of words in . So far a hashset can do the trick. However, it cannot provide search prefix in .
Note: One application for this data structure is for search engines and their auto completion functionalities.
class TrieNode {
public bool word; // isLeaf
public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
}
public class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
}
public void insert(string word) {
TrieNode curr = this.root;
foreach (char c in word) {
if (!curr.children.ContainsKey(c)) {
curr.children[c] = new TrieNode();
}
curr = curr.children[c];
}
curr.word = true;
}
public bool search(string word) {
TrieNode curr = this.root;
foreach (char c in word) {
if (!curr.children.ContainsKey(c)) {
return false;
}
curr = curr.children[c];
}
return curr.word;
}
public bool startsWith(string prefix) {
TrieNode curr = this.root;
foreach (char c in prefix) {
if (!curr.children.ContainsKey(c)) {
return false;
}
curr = curr.children[c];
}
return true;
}
Union Find
Union-Find is a useful tool for keeping track of nodes connected in a graph and detecting cycles in a graph. Of course, we can achieve this with DFS as well by using a hashset, call it, seen. However, DFS is a good choice when there is a static graph, i.e. no edges are added overtime. If we are adding edges overtime, that makes the graph dynamic, and Union-Find is a better choice.
public class UnionFind {
Dictionary<int, int> par;
Dictionary<int, int> rank;
public UnionFind(int n) {
par = new Dictionary<int, int>();
rank = new Dictionary<int, int>();
for (int i = 1; i < n + 1; i++) {
par[i] = i;
rank[i] = 0;
}
}
// Find parent of n, with path compression.
public int find(int n) {
int p = par[n];
while (p != par[p]) {
par[p] = par[par[p]];
p = par[p];
}
return p;
}
// Union by height / rank.
// Return false if already connected, true otherwise.
public bool union(int n1, int n2) {
int p1 = this.find(n1), p2 = this.find(n2);
if (p1 == p2) {
return false;
}
if (rank[p1] > rank[p2]) {
par[p2] = p1;
} else if (rank[p1] < rank[p2]) {
par[p1] = p2;
} else {
par[p1] = p2;
rank[p2] = rank[p2] + 1;
}
return true;
}
}
Segment Tree
Application: Let's say you have a list of index and an value and need to dynamically perform two operations:
- update(index, value)
- querySum(leftIndex, rightIndex)
With a prefix array and a regular array you can perform update in and then when required perform querySum in .
Segment Tree helps to perform both of in .
public class SegmentTree {
int sum;
SegmentTree left;
SegmentTree right;
int L;
int R;
public SegmentTree(int total, int L , int R) {
this.sum = total;
this.left = null;
this.right = null;
this.L = L;
this.R = R;
}
public static SegmentTree build(int[] nums, int L, int R) {
if (L == R) {
return new SegmentTree(nums[L], L, R);
}
int M = (L + R) / 2;
SegmentTree root = new SegmentTree(0, L, R);
root.left = SegmentTree.build(nums, L, M);
root.right = SegmentTree.build(nums, M + 1, R);
root.sum = root.left.sum + root.right.sum;
return root;
}
// O(logn)
public void update(int index, int val) {
if (this.L == this.R) {
this.sum = val;
return;
}
int M = (this.L + this.R) / 2;
if (index > M) {
this.right.update(index, val);
} else {
this.left.update(index, val);
}
this.sum = this.left.sum + this.right.sum;
}
// O(logn)
public int rangeQuery(int L, int R) {
if (L == this.L && R == this.R) {
return this.sum;
}
int M = (this.L + this.R) / 2;
if (L > M) {
return this.right.rangeQuery(L, R);
} else if (R <= M) {
return this.left.rangeQuery(L, R);
} else {
return (this.left.rangeQuery(L, M) +
this.right.rangeQuery(M + 1, R));
}
}
}
Iterative DFS
Iterative PreOrder DFS
public static IList<int> PreOrderTraversal(TreeNode root)
{
IList<int> result = new List<int>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0)
{
TreeNode node = stack.Pop();
result.Add(node.Val);
// Push right child first so that left child is processed first
if (node.Right != null)
{
stack.Push(node.Right);
}
if (node.Left != null)
{
stack.Push(node.Left);
}
}
return result;
}
Iterative InOrder DFS
public static IList<int> InOrderTraversal(TreeNode root)
{
IList<int> result = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while (curr != null || stack.Count > 0)
{
if (curr != null)
{
stack.Push(curr);
curr = curr.Left;
}
else
{
curr = stack.Pop();
result.Add(curr.Val);
curr = curr.Right;
}
}
return result;
}
Iterative PostOrder DFS
public static IList<int> PostOrderTraversal(TreeNode root)
{
IList<int> result = new List<int>();
if (root == null) return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode lastVisited = null;
while (stack.Count > 0 || root != null)
{
if (root != null)
{
stack.Push(root);
root = root.Left;
}
else
{
TreeNode peekNode = stack.Peek();
if (peekNode.Right != null && lastVisited != peekNode.Right)
{
root = peekNode.Right;
}
else
{
result.Add(peekNode.Val);
lastVisited = stack.Pop();
}
}
}
return result;
}
Two Heaps
Question: Implement a Median finder, where new values are inserted into the set, and you have to getMedian from that set. We will use two heaps one is MinHeap and the other is MaxHeap. MaxHeap will contain the first half of the (imaginary) current list and the MinHeap will contain the second half of it.
public class Median {
private PriorityQueue<int, int> small; // maxHeap
private PriorityQueue<int, int> large; // minHeap
public Median() {
// For the maxHeap, we invert the comparison to create a max-heap.
small = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
large = new PriorityQueue<int, int>();
}
}
public void Insert(int num) {
// Push to the max heap and swap with min heap if needed.
small.Enqueue(num, num);
if (small.Count > 0 && large.Count > 0 && small.Peek() > large.Peek()) {
var val = small.Dequeue();
large.Enqueue(val, val);
}
// Handle uneven size
if (small.Count > large.Count + 1) {
var val = small.Dequeue();
large.Enqueue(val, val);
} else if (large.Count > small.Count + 1) {
var val = large.Dequeue();
small.Enqueue(val, val);
}
}
public double GetMedian() {
if (small.Count > large.Count) {
return small.Peek();
} else if (large.Count > small.Count) {
return large.Peek();
}
// Even number of elements, return average of the two middle numbers.
return ((double)small.Peek() + large.Peek()) / 2;
}
Subsets:
Question: Given a list of distinct nums, return all possible distinct subsets.
// Time: O(n * 2^n), Space: O(n)
public static List<List<int>> SubsetsWithoutDuplicates(int[] nums) {
List<List<int>> subsets = new List<List<int>>();
List<int> curSet = new List<int>();
Helper(0, nums, curSet, subsets);
return subsets;
}
public static void Helper(int i, int[] nums, List<int> curSet, List<List<int>> subsets) {
if (i >= nums.Length) {
subsets.Add(new List<int>(curSet));
return;
}
// decision to include nums[i]
curSet.Add(nums[i]);
Helper(i + 1, nums, curSet, subsets);
curSet.RemoveAt(curSet.Count - 1);
// decision NOT to include nums[i]
Helper(i + 1, nums, curSet, subsets);
}
Question: Given a list of nums that are not necessarily distinct, return all possible distinct subsets.
// Time: O(n * 2^n), Space: O(n)
public static List<List<int>> SubsetsWithDuplicates(int[] nums) {
Array.Sort(nums);
List<int> curSet = new List<int>();
List<List<int>> subsets = new List<List<int>>();
Helper2(0, nums, curSet, subsets);
return subsets;
}
public static void Helper2(int i, int[] nums, List<int> curSet, List<List<int>> subsets) {
if (i >= nums.Length) {
subsets.Add(new List<int>(curSet));
return;
}
// decision to include nums[i]
curSet.Add(nums[i]);
Helper2(i + 1, nums, curSet, subsets);
curSet.RemoveAt(curSet.Count - 1);
// decision NOT to include nums[i]
while (i + 1 < nums.Length && nums[i] == nums[i + 1]) {
i++;
}
Helper2(i + 1, nums, curSet, subsets);
}
Time Space Complexity The time complexity would be because at every single element, we can either choose to include or not include that specific element. If we are given the list [1,2,3] to calculate all of the subsets for, we can only make two decisions at any given element and we are putting it all down in a decision tree, and 𝑛 n is the number of elements in set, it makes total sense that our algorithm runs in
The memory complexity should be considered the same, but sometimes the interviewer does not consider the input to be part of the time complexity. This would bring the space complexity to since n is not considered.
Combinations
Question: Given two nums n and k, return all possible combinations of size = k, choosing from values between 1 and n.
// Given n numbers (1 - n), return all possible combinations
// of size k. (n choose k math problem).
// Time: O(k * 2^n)
public static List<List<int>> Combinations(int n, int k) {
List<List<int>> combs = new List<List<int>>();
Helper(1, new List<int>(), combs, n, k);
return combs;
}
public static void Helper(int i, List<int> curComb, List<List<int>> combs, int n, int k) {
if (curComb.Count == k) {
combs.Add(new List<int>(curComb));
return;
}
if (i > n) {
return;
}
// decision to include i
curComb.Add(i);
Helper(i + 1, curComb, combs, n, k);
curComb.RemoveAt(curComb.Count - 1);
// decision to NOT include i
Helper(i + 1, curComb, combs, n, k);
}
Optimized Solution:
// Time: O(k * C(n, k))
public static List<List<int>> Combinations2(int n, int k) {
List<List<int>> combs = new List<List<int>>();
Helper2(1, new List<int>(), combs, n, k);
return combs;
}
public static void Helper2(int i, List<int> curComb, List<List<int>> combs, int n, int k) {
if (curComb.Count == k) {
combs.Add(new List<int>(curComb));
return;
}
if (i > n) {
return;
}
for (int j = i; j < n + 1; j++) {
curComb.Add(j);
Helper2(j + 1, curComb, combs, n, k);
curComb.RemoveAt(curComb.Count -1);
}
}
Permutation
Question: Given a list of nums, return all possible distinct permutations of nums.
// Time: O(n^2 * n!)
public static List<List<int>> GetPermutations(int[] nums)
{
List<List<int>> result = new();
Helper(nums, 0, nums.Length-1, result);
return result;
}
// Time: O(n^2 * n!)
public static void Helper(int[] array, int l, int right, List<List<int>> result) {
if (l == right) {
result.Add(array.ToList());
return;
}
for (int i=l; i<= right; i++) {
Swap(ref array[i], ref array[l]);
Helper(array, i+1, right, result);
Swap(ref array[i], ref array[l]);
}
}
public static void Swap(ref int i, ref int j) {
int tmp = i;
i = j;
j = tmp;
}