Parin's musings

LeetCode Problem Patterns and Associated Examples

1. Arrays and Strings

Common Patterns:

Two Pointers

  • Usage: Solve problems involving pairs in arrays or strings.

  • Examples:

    • LeetCode 26: Remove Duplicates from Sorted Array

      • Description: Remove duplicates in-place from a sorted array, allowing each element to appear only once.

    • LeetCode 125: Valid Palindrome

      • Description: Determine if a given string is a palindrome, considering only alphanumeric characters and ignoring cases.

    • LeetCode 11: Container With Most Water

      • Description: Find two lines that together with the x-axis form a container, such that the container contains the most water.

Sliding Window

  • Usage: Find subarrays or substrings within an array/string that satisfy certain conditions.

  • Examples:

    • LeetCode 3: Longest Substring Without Repeating Characters

      • Description: Find the length of the longest substring without repeating characters.

    • LeetCode 209: Minimum Size Subarray Sum

      • Description: Find the minimal length of a contiguous subarray of which the sum ≥ target value.

    • LeetCode 76: Minimum Window Substring

      • Description: Find the minimum window substring of s such that every character in t is included in the window.

Hash Tables / Dictionaries

  • Usage: Track frequency or existence of elements for quick lookups.

  • Examples:

    • LeetCode 1: Two Sum

      • Description: Find indices of the two numbers such that they add up to a specific target.

    • LeetCode 49: Group Anagrams

      • Description: Group a list of strings into anagrams.

    • LeetCode 242: Valid Anagram

      • Description: Determine if two strings are anagrams of each other.

Prefix Sum

  • Usage: Compute cumulative sums to answer range sum queries efficiently.

  • Examples:

    • LeetCode 560: Subarray Sum Equals K

      • Description: Find the total number of continuous subarrays whose sum equals to k.

    • LeetCode 523: Continuous Subarray Sum

      • Description: Check if the array has a continuous subarray of size at least two that sums up to a multiple of k.

    • LeetCode 303: Range Sum Query - Immutable

      • Description: Calculate the sum of elements between indices i and j inclusive.

2. Linked Lists

Common Patterns:

Fast and Slow Pointers

  • Usage: Detect cycles, find the middle node.

  • Examples:

    • LeetCode 141: Linked List Cycle

      • Description: Determine if a linked list has a cycle.

    • LeetCode 234: Palindrome Linked List

      • Description: Check if a singly linked list is a palindrome.

    • LeetCode 876: Middle of the Linked List

      • Description: Find the middle node of a linked list.

Reversal Techniques

  • Usage: Reverse entire or parts of linked lists.

  • Examples:

    • LeetCode 206: Reverse Linked List

      • Description: Reverse a singly linked list.

    • LeetCode 92: Reverse Linked List II

      • Description: Reverse a linked list from position m to n.

    • LeetCode 25: Reverse Nodes in k-Group

      • Description: Reverse nodes of a linked list k at a time.

Dummy Nodes

  • Usage: Simplify edge cases when modifying lists.

  • Examples:

    • LeetCode 19: Remove Nth Node From End of List

      • Description: Remove the nth node from the end of the list.

    • LeetCode 21: Merge Two Sorted Lists

      • Description: Merge two sorted linked lists.

    • LeetCode 203: Remove Linked List Elements

      • Description: Remove all elements from a linked list of integers that have value val.

3. Trees and Binary Trees

Common Patterns:

Depth-First Search (DFS)

  • Usage: Traverse trees to perform operations or checks.

  • Examples:

    • LeetCode 104: Maximum Depth of Binary Tree

      • Description: Find the maximum depth of a binary tree.

    • LeetCode 112: Path Sum

      • Description: Determine if the tree has a root-to-leaf path sum equal to a given number.

    • LeetCode 124: Binary Tree Maximum Path Sum

      • Description: Find the path with the maximum sum in a binary tree.

Breadth-First Search (BFS)

  • Usage: Level order traversal, shortest path in unweighted graphs.

  • Examples:

    • LeetCode 102: Binary Tree Level Order Traversal

      • Description: Return the level order traversal of a binary tree.

    • LeetCode 111: Minimum Depth of Binary Tree

      • Description: Find the minimum depth of a binary tree.

    • LeetCode 199: Binary Tree Right Side View

      • Description: Return the values of the nodes you can see ordered from top to bottom when looking from the right side.

Recursive Traversal

  • Usage: Inorder, preorder, postorder traversals using recursion.

  • Examples:

    • LeetCode 94: Binary Tree Inorder Traversal

      • Description: Return the inorder traversal of a binary tree.

    • LeetCode 144: Binary Tree Preorder Traversal

      • Description: Return the preorder traversal of a binary tree.

    • LeetCode 145: Binary Tree Postorder Traversal

      • Description: Return the postorder traversal of a binary tree.

Binary Search Tree (BST) Properties

  • Usage: Leverage BST properties for efficient searches.

  • Examples:

    • LeetCode 98: Validate Binary Search Tree

      • Description: Determine if a given tree is a valid BST.

    • LeetCode 230: Kth Smallest Element in a BST

      • Description: Find the kth smallest element in a BST.

    • LeetCode 235: Lowest Common Ancestor of a BST

      • Description: Find the lowest common ancestor of two nodes in a BST.

Tree Serialization and Deserialization

  • Usage: Convert trees to strings and vice versa.

  • Examples:

    • LeetCode 297: Serialize and Deserialize Binary Tree

      • Description: Serialize a binary tree to a string and deserialize it back.

4. Graphs

Common Patterns:

DFS and BFS Traversal

  • Usage: Explore all nodes in connected components.

  • Examples:

    • LeetCode 200: Number of Islands

      • Description: Count the number of islands in a 2D grid.

    • LeetCode 133: Clone Graph

      • Description: Clone an undirected graph.

    • LeetCode 695: Max Area of Island

      • Description: Find the maximum area of an island in a 2D grid.

Union-Find (Disjoint Set)

  • Usage: Detect cycles, find connected components.

  • Examples:

    • LeetCode 261: Graph Valid Tree

      • Description: Determine if an undirected graph is a valid tree.

    • LeetCode 721: Accounts Merge

      • Description: Merge accounts with common email addresses.

    • LeetCode 547: Number of Provinces

      • Description: Find the number of provinces (connected components) in a graph.

Topological Sort

  • Usage: Order tasks given dependencies.

  • Examples:

    • LeetCode 207: Course Schedule

      • Description: Determine if you can finish all courses given prerequisites.

    • LeetCode 210: Course Schedule II

      • Description: Find an order in which you can finish all courses.

    • LeetCode 269: Alien Dictionary

      • Description: Derive the order of letters in an alien language.

Dijkstra's Algorithm

  • Usage: Find shortest paths in weighted graphs.

  • Examples:

    • LeetCode 743: Network Delay Time

      • Description: Find the time it takes for all nodes to receive a signal from a starting node.

    • LeetCode 787: Cheapest Flights Within K Stops

      • Description: Find the cheapest price from source to destination with at most K stops.

    • LeetCode 1631: Path With Minimum Effort

      • Description: Find a path minimizing the maximum effort required.

5. Dynamic Programming (DP)

Common Patterns:

Memoization and Tabulation

  • Usage: Store intermediate results to avoid redundant calculations.

  • Examples:

    • LeetCode 70: Climbing Stairs

      • Description: Count ways to reach the top of stairs taking 1 or 2 steps.

    • LeetCode 509: Fibonacci Number

      • Description: Compute the nth Fibonacci number.

    • LeetCode 62: Unique Paths

      • Description: Find the number of unique paths in a grid.

State Definition and Transition

  • Usage: Define states and how they change.

  • Examples:

    • LeetCode 72: Edit Distance

      • Description: Find the minimum number of operations to convert one word to another.

    • LeetCode 1143: Longest Common Subsequence

      • Description: Find the length of the longest common subsequence between two strings.

    • LeetCode 198: House Robber

      • Description: Maximize robbery amount without robbing adjacent houses.

DP on Strings

  • Usage: Solve problems related to subsequences and substrings.

  • Examples:

    • LeetCode 5: Longest Palindromic Substring

      • Description: Find the longest palindromic substring in a string.

    • LeetCode 647: Palindromic Substrings

      • Description: Count how many palindromic substrings are in a string.

    • LeetCode 115: Distinct Subsequences

      • Description: Count the number of distinct subsequences of s equal to t.

DP on Trees

  • Usage: Apply DP techniques to tree structures.

  • Examples:

    • LeetCode 337: House Robber III

      • Description: Maximize robbery amount in a binary tree without alerting the police.

    • LeetCode 124: Binary Tree Maximum Path Sum

      • Description: Find the maximum path sum in a binary tree.

    • LeetCode 968: Binary Tree Cameras

      • Description: Determine the minimum number of cameras needed to monitor all nodes.

Knapsack Problems

  • Usage: Select items to maximize value under capacity constraints.

  • Examples:

    • LeetCode 416: Partition Equal Subset Sum

      • Description: Determine if an array can be partitioned into two subsets with equal sums.

    • LeetCode 494: Target Sum

      • Description: Find the number of ways to assign symbols to make the sum of integers equal to target S.

    • LeetCode 322: Coin Change

      • Description: Find the fewest number of coins needed to make up a given amount.

6. Backtracking

Common Patterns:

Permutation and Combination Generation

  • Usage: Generate all possible arrangements.

  • Examples:

    • LeetCode 46: Permutations

      • Description: Return all possible permutations of a list of numbers.

    • LeetCode 77: Combinations

      • Description: Return all possible combinations of k numbers out of 1...n.

    • LeetCode 78: Subsets

      • Description: Return all possible subsets of a set of numbers.

Constraint Satisfaction

  • Usage: Fill in values meeting specific conditions.

  • Examples:

    • LeetCode 51: N-Queens

      • Description: Place n queens on an n×n chessboard so that no two queens threaten each other.

    • LeetCode 37: Sudoku Solver

      • Description: Solve a Sudoku puzzle by filling the empty cells.

    • LeetCode 79: Word Search

      • Description: Determine if a word exists in a grid by moving horizontally or vertically.

Recursive Exploration

  • Usage: Explore all potential solutions recursively.

  • Examples:

    • LeetCode 39: Combination Sum

      • Description: Find all unique combinations where candidate numbers sum to target.

    • LeetCode 131: Palindrome Partitioning

      • Description: Partition a string such that every substring is a palindrome.

    • LeetCode 212: Word Search II

      • Description: Find all words in a grid from a list of words.

7. Greedy Algorithms

Common Patterns:

Activity Selection

  • Usage: Select maximum number of activities without overlap.

  • Examples:

    • LeetCode 45: Jump Game II

      • Description: Find the minimum number of jumps to reach the end of the array.

    • LeetCode 621: Task Scheduler

      • Description: Find the least number of units of times that the CPU will take to finish all the given tasks.

    • LeetCode 452: Minimum Number of Arrows to Burst Balloons

      • Description: Find the minimum number of arrows to burst all balloons.

Interval Problems

  • Usage: Merge or select intervals based on criteria.

  • Examples:

    • LeetCode 56: Merge Intervals

      • Description: Merge all overlapping intervals.

    • LeetCode 435: Non-overlapping Intervals

      • Description: Find the minimum number of intervals to remove to make the rest of the intervals non-overlapping.

    • LeetCode 253: Meeting Rooms II

      • Description: Find the minimum number of conference rooms required.

Optimal Substructure

  • Usage: Make the best choice at each step.

  • Examples:

    • LeetCode 135: Candy

      • Description: Distribute candies to children based on their ratings.

    • LeetCode 134: Gas Station

      • Description: Determine the starting gas station's index if you can travel around the circuit once.

    • LeetCode 406: Queue Reconstruction by Height

      • Description: Reconstruct the queue based on people's heights and the number of people in front.

8. Stacks and Queues

Common Patterns:

Monotonic Stack

  • Usage: Find next greater/smaller elements.

  • Examples:

    • LeetCode 84: Largest Rectangle in Histogram

      • Description: Find the area of the largest rectangle in a histogram.

    • LeetCode 739: Daily Temperatures

      • Description: For each day, find how many days to wait until a warmer temperature.

    • LeetCode 496: Next Greater Element I

      • Description: Find the next greater element for each element in the array.

Parentheses Matching

  • Usage: Validate or compute expressions with parentheses.

  • Examples:

    • LeetCode 20: Valid Parentheses

      • Description: Determine if the input string has valid parentheses.

    • LeetCode 32: Longest Valid Parentheses

      • Description: Find the length of the longest valid (well-formed) parentheses substring.

    • LeetCode 301: Remove Invalid Parentheses

      • Description: Remove the minimum number of invalid parentheses to make the input string valid.

Implement Data Structures

  • Usage: Build queues using stacks or vice versa.

  • Examples:

    • LeetCode 232: Implement Queue using Stacks

      • Description: Implement a queue using two stacks.

    • LeetCode 225: Implement Stack using Queues

      • Description: Implement a stack using two queues.

    • LeetCode 155: Min Stack

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

9. Heaps and Priority Queues

Common Patterns:

Top K Elements

  • Usage: Find the largest or smallest K elements.

  • Examples:

    • LeetCode 215: Kth Largest Element in an Array

      • Description: Find the kth largest element in an unsorted array.

    • LeetCode 347: Top K Frequent Elements

      • Description: Return the k most frequent elements.

    • LeetCode 703: Kth Largest Element in a Stream

      • Description: Design a class to find the kth largest element in a stream.

Merge K Sorted Lists/Arrays

  • Usage: Efficiently merge multiple sorted lists.

  • Examples:

    • LeetCode 23: Merge k Sorted Lists

      • Description: Merge k sorted linked lists into one sorted list.

    • LeetCode 378: Kth Smallest Element in a Sorted Matrix

      • Description: Find the kth smallest element in a sorted matrix.

    • LeetCode 295: Find Median from Data Stream

      • Description: Continuously find the median of a number stream.

Scheduling Problems

  • Usage: Assign tasks based on priority.

  • Examples:

    • LeetCode 767: Reorganize String

      • Description: Rearrange the string so that no two adjacent characters are the same.

    • LeetCode 253: Meeting Rooms II

      • Description: Find the minimum number of conference rooms required.

    • LeetCode 621: Task Scheduler

      • Description: Find the least number of units of times that the CPU will take to finish all the given tasks.

10. Binary Search

Common Patterns:

Search in Sorted Arrays

  • Usage: Efficiently find elements in sorted structures.

  • Examples:

    • LeetCode 704: Binary Search

      • Description: Implement binary search to find the position of a target value.

    • LeetCode 35: Search Insert Position

      • Description: Find the index where a target should be inserted in a sorted array.

    • LeetCode 374: Guess Number Higher or Lower

      • Description: Guess the number chosen by a higher or lower hint.

Modified Binary Search

  • Usage: Apply binary search in rotated or complex arrays.

  • Examples:

    • LeetCode 33: Search in Rotated Sorted Array

      • Description: Search for a target value in a rotated sorted array.

    • LeetCode 81: Search in Rotated Sorted Array II

      • Description: Search in a rotated sorted array that may contain duplicates.

    • LeetCode 153: Find Minimum in Rotated Sorted Array

      • Description: Find the minimum element in a rotated sorted array.

Answer Range Problems

  • Usage: Use binary search to find optimal value satisfying conditions.

  • Examples:

    • LeetCode 875: Koko Eating Bananas

      • Description: Find the minimum eating speed to finish bananas within h hours.

    • LeetCode 1011: Capacity To Ship Packages Within D Days

      • Description: Find the least weight capacity to ship all packages within D days.

    • LeetCode 410: Split Array Largest Sum

      • Description: Split the array into m subarrays minimizing the largest sum among them.

11. Trie (Prefix Tree)

Common Patterns:

Prefix Search

  • Usage: Store and search words efficiently by prefixes.

  • Examples:

    • LeetCode 208: Implement Trie (Prefix Tree)

      • Description: Implement a trie with insert, search, and startsWith methods.

    • LeetCode 211: Add and Search Word - Data structure design

      • Description: Design a data structure that supports adding new words and finding if a string matches any previously added string.

    • LeetCode 648: Replace Words

      • Description: Replace words in a sentence with their root forms.

Autocomplete Systems

  • Usage: Suggest words based on input prefixes.

  • Examples:

    • LeetCode 642: Design Search Autocomplete System

      • Description: Implement an autocomplete system that suggests hot sentences.

Word Break Problems

  • Usage: Determine if a string can be segmented into words.

  • Examples:

    • LeetCode 139: Word Break

      • Description: Determine if a string can be segmented into a space-separated sequence of dictionary words.

    • LeetCode 212: Word Search II

      • Description: Find all words in a grid from a list of words.

    • LeetCode 425: Word Squares

      • Description: Find all valid word squares from a list of words.

12. Bit Manipulation

Common Patterns:

Bitwise Operations

  • Usage: Perform operations using bits for efficiency.

  • Examples:

    • LeetCode 136: Single Number

      • Description: Find the element that appears only once in an array where every other element appears twice.

    • LeetCode 338: Counting Bits

      • Description: Count the number of set bits for every number up to n.

    • LeetCode 190: Reverse Bits

      • Description: Reverse bits of a given 32 bits unsigned integer.

Masking Techniques

  • Usage: Use bit masks for subsets and combinations.

  • Examples:

    • LeetCode 78: Subsets

      • Description: Return all possible subsets of a set of numbers.

    • LeetCode 201: Bitwise AND of Numbers Range

      • Description: Find the bitwise AND of all numbers in a given range.

    • LeetCode 421: Maximum XOR of Two Numbers in an Array

      • Description: Find the maximum result of nums[i] XOR nums[j].

Parity Checks

  • Usage: Check if number of set bits is odd or even.

  • Examples:

    • LeetCode 191: Number of 1 Bits

      • Description: Write a function that takes an unsigned integer and returns the number of '1' bits.

    • LeetCode 231: Power of Two

      • Description: Check if a number is a power of two.

    • LeetCode 461: Hamming Distance

      • Description: Calculate the Hamming distance between two integers.

13. Math and Number Theory

Common Patterns:

Prime Numbers and Factors

  • Usage: Work with primes, divisibility.

  • Examples:

    • LeetCode 204: Count Primes

      • Description: Count the number of prime numbers less than a non-negative number, n.

    • LeetCode 263: Ugly Number

      • Description: Determine if a number is an ugly number (only prime factors of 2, 3, 5).

    • LeetCode 202: Happy Number

      • Description: Determine if a number is a happy number.

Modular Arithmetic

  • Usage: Handle large numbers with modulo operations.

  • Examples:

    • LeetCode 50: Pow(x, n)

      • Description: Implement pow(x, n), calculating x raised to the power n.

    • LeetCode 43: Multiply Strings

      • Description: Multiply two non-negative integers represented as strings.

    • LeetCode 372: Super Pow

      • Description: Calculate (a^b) mod 1337 where b is a large integer given in the form of an array.

Probability and Statistics

  • Usage: Random sampling, shuffling.

  • Examples:

    • LeetCode 382: Linked List Random Node

      • Description: Implement a method to randomly select a node's value from a linked list.

    • LeetCode 384: Shuffle an Array

      • Description: Shuffle a set of numbers without duplicates.

    • LeetCode 398: Random Pick Index

      • Description: Given an array containing duplicates, randomly output the index of a given target number.

14. Design Problems

Common Patterns:

LRU Cache Implementation

  • Usage: Use hash maps and doubly-linked lists.

  • Examples:

    • LeetCode 146: LRU Cache

      • Description: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

    • LeetCode 460: LFU Cache

      • Description: Design a data structure that follows the constraints of a Least Frequently Used (LFU) cache.

Concurrency Control

  • Usage: Manage multi-threading.

  • Examples:

    • LeetCode 1115: Print FooBar Alternately

      • Description: Print "foo" and "bar" alternately using two threads.

    • LeetCode 1114: Print in Order

      • Description: Ensure threads print in order.

    • LeetCode 1188: Design Bounded Blocking Queue

      • Description: Implement a thread-safe bounded blocking queue.

Scalable System Design

  • Usage: Design systems that can handle large amounts of data.

  • Examples:

    • LeetCode 362: Design Hit Counter

      • Description: Design a hit counter which counts the number of hits in the past 5 minutes.

    • LeetCode 295: Find Median from Data Stream

      • Description: Continuously find the median of a number stream.

    • LeetCode 642: Design Search Autocomplete System

      • Description: Implement an autocomplete system that suggests hot sentences.

15. Recursion and Divide & Conquer

Common Patterns:

Recursive Tree Traversal

  • Usage: Break down tree problems recursively.

  • Examples:

    • LeetCode 104: Maximum Depth of Binary Tree

      • Description: Find the maximum depth of a binary tree.

    • LeetCode 101: Symmetric Tree

      • Description: Check if a binary tree is symmetric.

    • LeetCode 112: Path Sum

      • Description: Determine if the tree has a root-to-leaf path sum equal to a given number.

Divide and Conquer

  • Usage: Break problems into subproblems.

  • Examples:

    • LeetCode 169: Majority Element

      • Description: Find the majority element that appears more than n/2 times.

    • LeetCode 53: Maximum Subarray

      • Description: Find the contiguous subarray with the largest sum.

    • LeetCode 4: Median of Two Sorted Arrays

      • Description: Find the median of two sorted arrays.

Matrix Multiplication and Search

  • Usage: Apply recursion to 2D arrays.

  • Examples:

    • LeetCode 240: Search a 2D Matrix II

      • Description: Write an efficient algorithm that searches for a value in an m x n matrix.

    • LeetCode 37: Sudoku Solver

      • Description: Solve a Sudoku puzzle by filling the empty cells.

    • LeetCode 74: Search a 2D Matrix

      • Description: Search for a target value in a sorted 2D matrix.

16. Hashing

Common Patterns:

Frequency Counting

  • Usage: Count occurrences efficiently.

  • Examples:

    • LeetCode 347: Top K Frequent Elements

      • Description: Return the k most frequent elements.

    • LeetCode 169: Majority Element

      • Description: Find the majority element that appears more than n/2 times.

    • LeetCode 451: Sort Characters By Frequency

      • Description: Sort characters in decreasing order based on frequency.

Hash Set for Uniqueness

  • Usage: Ensure elements are unique or detect duplicates.

  • Examples:

    • LeetCode 217: Contains Duplicate

      • Description: Determine if the array contains any duplicates.

    • LeetCode 128: Longest Consecutive Sequence

      • Description: Find the length of the longest consecutive elements sequence.

    • LeetCode 219: Contains Duplicate II

      • Description: Check if there are duplicates within a certain index distance.

Mapping Relationships

  • Usage: Map keys to values in problems involving relationships.

  • Examples:

    • LeetCode 205: Isomorphic Strings

      • Description: Determine if two strings are isomorphic.

    • LeetCode 290: Word Pattern

      • Description: Check if a pattern matches a string.

    • LeetCode 138: Copy List with Random Pointer

      • Description: Create a deep copy of a linked list with random pointers.

17. Sliding Window

Common Patterns:

Fixed Size Window

  • Usage: Move window over array/string to check conditions.

  • Examples:

    • LeetCode 643: Maximum Average Subarray I

      • Description: Find the contiguous subarray of given length k that has the maximum average.

    • LeetCode 1052: Grumpy Bookstore Owner

      • Description: Maximize the number of customers that can be satisfied.

    • LeetCode 1004: Max Consecutive Ones III

      • Description: Find the maximum number of consecutive 1's in the array if you can flip at most k zeros.

Variable Size Window

  • Usage: Adjust window size based on conditions.

  • Examples:

    • LeetCode 76: Minimum Window Substring

      • Description: Find the minimum window substring of s that contains all the characters of t.

    • LeetCode 3: Longest Substring Without Repeating Characters

      • Description: Find the length of the longest substring without repeating characters.

    • LeetCode 159: Longest Substring with At Most Two Distinct Characters

      • Description: Find the length of the longest substring that contains at most two distinct characters.

18. String Manipulation

Common Patterns:

Two Pointer Technique

  • Usage: Process strings from both ends.

  • Examples:

    • LeetCode 125: Valid Palindrome

      • Description: Determine if a string is a palindrome considering only alphanumeric characters.

    • LeetCode 344: Reverse String

      • Description: Reverse a string.

    • LeetCode 345: Reverse Vowels of a String

      • Description: Reverse only the vowels of a string.

String Parsing

  • Usage: Parse and evaluate strings.

  • Examples:

    • LeetCode 224: Basic Calculator

      • Description: Implement a basic calculator to evaluate a simple expression string.

    • LeetCode 227: Basic Calculator II

      • Description: Implement a basic calculator to evaluate a simple expression string with +, -, *, / operators.

    • LeetCode 394: Decode String

      • Description: Decode a string encoded with k[encoded_string] format.

Pattern Matching

  • Usage: Match patterns using algorithms.

  • Examples:

    • LeetCode 28: Implement strStr()

      • Description: Implement strstr() to find the index of the first occurrence of a substring.

    • LeetCode 10: Regular Expression Matching

      • Description: Implement regular expression matching with support for '.' and '*'.

    • LeetCode 44: Wildcard Matching

      • Description: Implement wildcard pattern matching with support for '?' and '*'.

19. Geometry and Coordinate Problems

Common Patterns:

Sweep Line Algorithm

  • Usage: Process points in order.

  • Examples:

    • LeetCode 218: The Skyline Problem

      • Description: Find the skyline formed by a set of buildings.

    • LeetCode 253: Meeting Rooms II

      • Description: Find the minimum number of conference rooms required.

    • LeetCode 352: Data Stream as Disjoint Intervals

      • Description: Given a data stream input, output the data as disjoint intervals.

Coordinate Transformation

  • Usage: Convert between coordinate systems.

  • Examples:

    • LeetCode 48: Rotate Image

      • Description: Rotate a 2D matrix by 90 degrees.

    • LeetCode 149: Max Points on a Line

      • Description: Find the maximum number of points that lie on the same straight line.

    • LeetCode 835: Image Overlap

      • Description: Find the largest possible overlap between two binary images.

Area and Distance Calculations

  • Usage: Compute geometric properties.

  • Examples:

    • LeetCode 84: Largest Rectangle in Histogram

      • Description: Find the area of the largest rectangle in a histogram.

    • LeetCode 223: Rectangle Area

      • Description: Find the total area covered by two rectilinear rectangles.

    • LeetCode 963: Minimum Area Rectangle II

      • Description: Find the minimum area of a rectangle formed from points.

20. Combinatorics and Probability

Common Patterns:

Counting Techniques

  • Usage: Count combinations or permutations.

  • Examples:

    • LeetCode 62: Unique Paths

      • Description: Find the number of unique paths from top-left to bottom-right in a grid.

    • LeetCode 1079: Letter Tile Possibilities

      • Description: Count the number of possible sequences of letters you can make.

    • LeetCode 1641: Count Sorted Vowel Strings

      • Description: Count the number of strings of length n that consist of vowels and are lexicographically sorted.

Probability Calculations

  • Usage: Compute likelihoods.

  • Examples:

    • LeetCode 528: Random Pick with Weight

      • Description: Randomly pick an index based on weight.

    • LeetCode 470: Implement Rand10() Using Rand7()

      • Description: Use rand7() to implement rand10().

    • LeetCode 497: Random Point in Non-overlapping Rectangles

      • Description: Randomly pick a point from given non-overlapping rectangles.

Preparation Tips:

  • Understand Fundamental Concepts: Ensure you have a strong grasp of basic data structures and algorithms.
  • Practice Common Patterns: Solve multiple problems of each pattern to recognize them quickly during interviews.
  • Time and Space Complexity: Always analyze and aim to optimize your solutions.
  • Write Clean Code: Practice writing syntactically correct and efficient code.
  • Edge Cases and Testing: Consider edge cases and test your code thoroughly.
  • Discuss Trade-offs: Be prepared to discuss different approaches and their trade-offs.

By focusing on these patterns and practicing problems associated with each, you'll be better prepared to tackle a wide range of interview questions effectively. Good luck with your interview preparation!

Leet code patterns with problems Published on 2024-09-27