Back To Module Home

Coding Interview Patterns

0% completed

Sliding Window

Sliding Window: Introduction Repeated DNA Sequences Solution: Repeated DNA Sequences Find Maximum in Sliding Window Solution: Find Maximum in Sliding Window Minimum Window Subsequence Solution: Minimum Window Subsequence Longest Repeating Character Replacement Solution: Longest Repeating Character Replacement Minimum Window Substring Solution: Minimum Window Substring Longest Substring without Repeating Characters Solution: Longest Substring without Repeating Characters Minimum Size Subarray Sum Solution: Minimum Size Subarray Sum Best Time to Buy and Sell Stock

Two Pointers

Two Pointers: Introduction Valid Palindrome Solution: Valid Palindrome Sum of Three Values Solution: Sum of Three Values Remove nth Node from End of List Solution: Remove nth Node from End of List Sort Colors Solution: Sort Colors Reverse Words in a String Solution: Reverse Words in a String Valid Palindrome II

Fast and Slow Pointer

Fast and Slow Pointers: Introduction Happy Number Solution: Happy Number Linked List Cycle Solution: Linked List Cycle Middle of the Linked List Solution: Middle of the Linked List Circular Array Loop Solution: Circular Array Loop Find The Duplicate Number Solution: Find The Duplicate Number Palindrome Linked List Solution: Palindrome Linked List

Merge Intervals

Merge Intervals: Introduction Merge Intervals Solution: Merge Intervals Insert Interval Solution: Insert Interval Interval List Intersections Solution: Interval List Intersections Employee Free Time Solution: Employee Free Time Task Scheduler Solution: Task Scheduler Meeting Rooms II

In-place Reversal of a Linked List

In-place Reversal of a Linked List: Introduction Reverse Linked List Solution: Reverse Linked List Reverse Nodes in k-Group Solution: Reverse Nodes in k-Group Reverse Linked List II Solution: Reverse Linked List II Reorder List Solution: Reorder List Swapping Nodes in a Linked List Solution: Swapping Nodes in a Linked List Reverse Nodes In Even Length Groups Solution: Reverse Nodes in Even Length Groups Swap Nodes in Pairs

Two Heaps

Two Heaps: Introduction Maximize Capital Solution: Maximize Capital Sliding Window Median Solution: Sliding Window Median Find Median from a Data Stream Solution: Find Median from a Data Stream Schedule Tasks on Minimum Machines Solution: Schedule Tasks on Minimum Machines

K-way merge

K-way Merge: Introduction

Merge Sorted Array

Solution: Merge Sorted Array

Kth Smallest Number in M Sorted Lists

Solution: Kth Smallest Number in M Sorted Lists

Find K Pairs with Smallest Sums

Solution: Find K Pairs with Smallest Sums

Merge K Sorted Lists

Solution: Merge K Sorted Lists

Kth Smallest Element in a Sorted Matrix

Solution: Kth Smallest Element in a Sorted Matrix

Top K Elements

Top K Elements: Introduction Kth Largest Element in a Stream Solution: Kth Largest Element in a Stream Reorganize String Solution: Reorganize String K Closest Points to Origin Solution: K Closest Points to Origin Top K Frequent Elements Solution: Top K Frequent Elements Kth Largest Element in an Array Solution: Kth Largest Element in an Array Top K Frequent Words

Modified Binary Search

Modified Binary Search: Introduction Binary Search Solution: Binary Search Search in Rotated Sorted Array Solution: Search in Rotated Sorted Array First Bad Version Solution: First Bad Version Random Pick with Weight Solution: Random Pick with Weight Find K Closest Elements Solution: Find K Closest Elements Single Element in a Sorted Array Solution: Single Element in a Sorted Array Search in Rotated Sorted Array II

Subsets

Subsets: Introduction Subsets Solution: Subsets Permutations Solution: Permutations Letter Combinations of a Phone Number Solution: Letter Combinations of a Phone Number Generate Parentheses Solution: Generate Parentheses Find K-Sum Subsets

Greedy Techniques

Greedy Techniques: Introduction Jump Game I Solution: Jump Game I Boats to Save People Solution: Boats to Save People Gas Stations Solution: Gas Stations Two City Scheduling Solution: Two City Scheduling Minimum Number of Refueling Stops Solution: Minimum Number of Refueling Stops Jump Game II

Backtracking

Backtracking: Introduction N-Queens Solution: N-Queens Word Search Solution: Word Search House Robber III Solution: House Robber III Restore IP Addresses Solution: Restore IP Addresses Flood Fill Solution: Flood Fill Sudoku Solver Matchsticks to Square

Dynamic Programming

Dynamic Programming: Introduction 0/1 Knapsack Solution: 0/1 Knapsack Coin Change Solution: Coin Change N-th Tribonacci Number Solution: N-th Tribonacci Number Partition Equal Subset Sum Solution: Partition Equal Subset Sum Counting Bits Solution: Counting Bits 01 Matrix Solution: 01 Matrix House Robber II Solution: House Robber II Maximum Product Subarray Solution: Maximum Product Subarray Combination Sum Solution: Combination Sum Word Break Solution: Word Break Palindromic Substrings Solution: Palindromic Substrings Longest Common Subsequence Solution: Longest Common Subsequence Word Break II Solution: Word Break II Decode Ways Solution: Decode Ways Climbing Stairs

Cyclic Sort

Cyclic Sort: Introduction Missing Number Solution: Missing Number First Missing Positive Solution: First Missing Positive Find The Duplicate Number Solution: Find The Duplicate Number Find the Corrupt Pair Solution: Find the Corrupt Pair Find the First K Missing Positive Numbers

Topological Sort

Topological Sort: Introduction Compilation Order Solution: Compilation Order Alien Dictionary Solution: Alien Dictionary Verifying an Alien Dictionary Solution: Verifying an Alien Dictionary Course Schedule II Solution: Course Schedule II Course Schedule Solution: Course Schedule Find All Possible Recipes from Given Supplies

Matrices

Matrices: Introduction Set Matrix Zeros Solution: Set Matrix Zeros Rotate Image Solution: Rotate Image Spiral Matrix Solution: Spiral Matrix Where Will the Ball Fall Solution: Where Will the Ball Fall

Stacks

Stacks: Introduction Basic Calculator Solution: Basic Calculator Remove All Adjacent Duplicates In String Solution: Remove All Adjacent Duplicates In String Minimum Remove to Make Valid Parentheses Solution: Minimum Remove to Make Valid Parentheses Exclusive Execution Time of Functions Solution: Exclusive Execution Time of Functions Flatten Nested List Iterator Solution: Flatten Nested List Iterator Implement Queue Using Stacks Solution: Implement Queue Using Stacks Valid Parentheses

Graphs

Graphs: Introduction Network Delay Time Solution: Network Delay Time Paths in Maze That Lead to Same Room Solution: Paths in Maze That Lead to Same Room Clone Graph Solution: Clone Graph Graph Valid Tree Solution: Graph Valid Tree Bus Routes Solution: Bus Routes

Tree Depth First Search

Tree Depth-first Search: Introduction Flatten Binary Tree to Linked List Solution: Flatten Binary Tree to Linked List Diameter of Binary Tree Solution: Diameter of Binary Tree Serialize and Deserialize Binary Tree Solution: Serialize and Deserialize Binary Tree Invert Binary Tree Solution: Invert Binary Tree Binary Tree Maximum Path Sum Solution: Binary Tree Maximum Path Sum Convert Sorted Array to Binary Search Tree Solution: Convert Sorted Array to Binary Search Tree Solution: Build Binary Tree from Preorder and Inorder Traversal Build Binary Tree from Preorder and Inorder Traversal Binary Tree Right Side View Solution: Binary Tree Right Side View Lowest Common Ancestor of a Binary Tree Solution: Lowest Common Ancestor of a Binary Tree Validate Binary Search Tree Solution: Validate Binary Search Tree Maximum Depth of Binary Tree Kth Smallest Element in a BST

Tree Breadth First Search

Tree Breadth-first Search: Introduction Level Order Traversal of Binary Tree Solution: Level Order Traversal of Binary Tree Binary Tree Zigzag Level Order Traversal Solution: Binary Tree Zigzag Level Order Traversal Populating Next Right Pointers in Each Node Solution: Populating Next Right Pointers in Each Node Vertical Order Traversal of a Binary Tree Solution: Vertical Order Traversal of a Binary Tree Symmetric Tree Solution: Symmetric Tree Word Ladder Solution: Word Ladder Connect All Siblings of a Binary Tree

Trie

Trie: Introduction Implement Trie Solution: Implement Trie Search Suggestions System Solution: Search Suggestions System Replace Words Solution: Replace Words Design Add and Search Words Data Structure Solution: Design Add and Search Words Data Structure Word Search II Solution: Word Search II Lexicographical Numbers

Hash Maps

Hash Maps: Introduction Design HashMap Solution: Design HashMap Fraction to Recurring Decimal Solution: Fraction to Recurring Decimal Logger Rate Limiter Solution: Logger Rate Limiter Next Greater Element Solution: Next Greater Element Isomorphic Strings Solution: Isomorphic Strings Longest Palindrome

Knowing What to Track

Knowing What to Track: Introduction Palindrome Permutation Solution: Palindrome Permutation Valid Anagram Solution: Valid Anagram Design Tic-Tac-Toe Solution: Design Tic-Tac-Toe Group Anagrams Solution: Group Anagrams Maximum Frequency Stack Solution: Maximum Frequency Stack First Unique Character in a String Solution: First Unique Character in a String Find All Anagrams in a String Solution: Find All Anagrams in a String Longest Palindrome by Concatenating Two-Letter Words Solution: Longest Palindrome by Concatenating Two-Letter Words Ransom Note

Union Find

Union Find: Introduction Redundant Connection Solution: Redundant Connection Number of Islands Solution: Number of Islands Most Stones Removed with Same Row or Column Solution: Most Stones Removed with Same Row or Column Longest Consecutive Sequence Solution: Longest Consecutive Sequence Last Day Where You Can Still Cross Solution: Last Day Where You Can Still Cross Regions Cut by Slashes Solution: Regions Cut by Slashes Minimize Malware Spread Solution: Minimize Malware Spread Accounts Merge Solution: Accounts Merge Minimize Malware Spread Solution: Minimize Malware Spread Evaluate Division

Custom Data Structures

Custom Data Structures: Introduction Snapshot Array Solution: Snapshot Array Time-Based Key-Value Store Solution: Time-Based Key-Value Store Implement LRU Cache Solution: Implement LRU Cache Insert Delete GetRandom O(1)Solution: Insert Delete GetRandom O(1)Min Stack Solution: Min Stack LFU Cache

Bitwise Manipulation

Bitwise Manipulation: Introduction Find the Difference Solution: Find the Difference Complement of Base 10 Number Solution: Complement of Base 10 Number Flipping an Image Solution: Flipping an Image Single Number Solution: Single Number Two Single Numbers Solution: Two Single Numbers Encode and Decode Strings Solution: Encode and Decode Strings Reverse Bits

Challenge Yourself

Challenge Yourself: Introduction Shortest Bridge Number of Connected Components in an Undirected Graph Median of Two Sorted Arrays Pacific Atlantic Water Flow Contains Duplicate Two Sum Find Minimum in Rotated Sorted Array Non-overlapping Intervals Meeting Rooms Largest Rectangle in Histogram Subtree of Another Tree Sort List Number of 1 Bits Container With the Most Water Evaluate Reverse Polish Notation 4Sum Loud and Rich Product of Array Except Self Longest Increasing Subsequence Sum of Two Integers Majority Element Unique Paths Longest Palindromic Substring Permutations II Number of Provinces Linked List Cycle II Minimum Flips to Make the Binary String Alternate Lemonade Change House Robber Find All Numbers Disappeared in an Array Find All Duplicates in an Array Same Tree Design In-Memory File System Design File System Asteroid Collision Rotting Oranges Maximum Subarray Top K Frequent Words Add Binary Multiply Strings

Conclusion

...

/

Solution: Kth Smallest Number in M Sorted Lists

Solution: Kth Smallest Number in M Sorted Lists

Let's solve the Kth Smallest Number in M Sorted Lists problem using the K-Way Merge pattern.

Statement

Given a list, lists, containing $m$ sorted lists of integers in ascending order, and an integer k, find the $k^{th}$ smallest element among all the lists.

Even if some values appear multiple times across the lists, each occurrence is treated as a unique element when determining the $k^{th}$ smallest number.

If k exceeds the total number of elements across all lists, return the largest element among them. If the lists are empty, return 0.

Constraints:

$1\leq m \leq50$
$0\leq$ lists[i].length $\leq 50$
$-10^9\leq$ lists[i][j] $\leq 10^9$

...