Competetive_Coding_handbook
Competetive_Coding_handbook
IARE
INSTITUTE OF
Career Development Center
AERONAUTICAL ENGINEERING
COMPETITIVE PROGRAMMING
HANDBOOK
By
Dr. Padmaja B
COMPETITIVE PROGRAMMING HAND BOOK
Prepared by
Dr. B. Padmaja
Associate Professor
CONTENTS
S No. Topic Name Page No.
1. Searching 12
a. Search Insert Position
b. Search a 2D Matrix
c. Search in Rotated Sorted Array
d. Find First and Last Position of Element in Sorted Array
e. Missing Number
2. Sorting 14
a. Relative Ranks
b. Array Partition
c. Longest Harmonious Subsequence
d. Fair Candy Swap
e. Sort Array by Parity
f. Matrix Cells in Distance Order
g. Two City Scheduling
h. Merge Sorted Array
i. Insertion Sort List
j. Kth Smallest Element in a Sorted Matrix
3. Cyclic Sort 19
a. Find All Duplicates in an Array
b. Find All Numbers Disappeared in an Array
c. Missing Number
d. First Missing Positive
4. Topological Sort 20
a. Find All Possible Recipes from Given Supplies
b. Maximum Employees to be Invited to a Meeting
c. Longest Cycle in a Graph
d. Build a Matrix with Conditions
e. Count Ways to Build Rooms in an Ant Colony
5. Strings 25
a. Longest Common Prefix
b. Count and Say
c. Group Anagrams
d. Restore IP Addresses
e. Interleaving String
f. Word Break
g. Isomorphic Strings
h. Bulls and Cows
i. Remove Duplicate Letters
j. Maximum Product of Word Lengths
k. Zigzag Conversion
6. Stacks and Queues 30
a. Evaluate Reverse Polish Notation
b. Min Stack
1|Page
c. Implement Queue using Stacks
d. Remove Duplicate Letters
e. Verify Preorder Serialization of a Binary Tree
f. Mini Parser
g. Decode String
h. Next Greater Element I
i. Baseball Game
j. Maximum Binary tree
k. Daily Temperatures
l. Validate Stack Sequences
m. Minimum Cost Tree from Leaf Values
n. Build an Array with Stack Operations
o. The Number of Weak Characters in the Game
p. Number of Visible People in a Queue
q. Number of People Aware of a Secret
r. Reveal Cards in Increasing Order
s. Find the Winner of the Circular Game
t. Design Circular Deque
7. Node Based Data Structures 45
a. Remove Linked List Elements
b. Reverse Linked List
c. Palindrome Linked List
d. Middle of the Linked List
e. Convert Binary Number in a Linked List to Integer
f. Intersection of Two Linked Lists
g. Delete Node in a Linked List
h. Odd Even Linked List
i. Design Twitter
j. Linked List Random Node
k. Swapping Nodes in a Linked List
l. Split Linked List in Parts
m. Next Greater Node in Linked List
n. Merge in Between Linked Lists
o. Maximum Twin Sum of a Linked List
p. Merge Nodes in Between Zeros
q. Remove Nodes from Linked List
r. Insert Greatest Common Divisors in Linked List
s. Rotate List
t. Partition List
8. Bit Manipulation 58
a. Raising Bacteria
b. And Then There Were K
c. Count Set Bits in an Integer
d. Rotate Bits of a Number
e. Find the Integer Occurring Odd Number of Times
f. Generating all the Subsets of an Integer Set
g. Number of Steps to Reduce a Number to Zero
h. Minimum Bit Flips to Convert Number
9. Heaps 62
a. Kth Largest Element in an Array
b. Sort Characters by Frequency
2|Page
c. Swim in Rising Water
d. Car Pooling
e. Avoid Flood in the City
10. HashMap 65
a. The Skyline Problem
b. Sliding Window Median
c. Smallest Range Covering Elements from K Lists
d. Cut off Trees for Golf Event
e. Find K Closest Elements
f. Minimum Cost to Hire K Workers
g. Minimum Numbers of Refueling Stops
h. Distant Barcodes
i. Dinner Plate Stacks
j. Maximum Number of Eaten Apples
11. Two Pointers 72
a. Count Pairs whose Sum is less than Target
b. Lexicographically Smallest Palindrome
c. Merge Two 2D Arrays by Summing Values
d. Find the Array Concatenation Value
e. Largest Positive Integer that Exists with its Negative
f. Maximum Matching of Players with Trainers
g. Strictly Palindromic Number
h. Number of Arithmetic Triplets
i. Rearrange Array Elements by Sign
j. Find First Palindromic String in the Array
k. Minimum Number of Swaps to Make the String Balanced
l. Merge Strings Alternately
m. Find the Distance Value Between Two Arrays
n. Container with Most Water
o. Flipping an Image
p. Shortest Distance to a Character
q. Count Binary Substrings
r. Two Sum IV - Input is a BST
s. Find the Duplicate Number
t. Happy Number
12. Range Queries 84
a. Range Sum Query – Mutable
b. Range Sum Query – Immutable
c. Range Frequency Queries
d. Range Product Queries of Powers
e. Count of Range Sum
13. Trie 86
a. Implement Trie (Prefix Tree)
b. Design Add and Search Words Data Structure
c. Lexicographical Numbers
d. Replace Words
e. Implement Magic Dictionary
f. Map Sum Pairs
g. Longest Word in Dictionary
h. Prefix and Suffix Search
i. Distinct Echo Substrings
3|Page
j. Remove Sub-Folders from the Filesystem
14. Fast and Slow Pointers 91
a. Middle of the Linked List
b. Linked List Cycle
c. Floyd’s Cycle Finding Algorithm
d. Remove Nth Node from End of List
15. Sliding Window 93
a. Find the K-Beauty of a Number
b. Maximum Erasure Value
c. Longest Nice Substring
d. Substrings of Size Three with Distinct Characters
e. Minimum Difference between Highest and Lowest of K Scores
f. Minimum Recolors to Get K Consecutive Black Blocks
g. Minimum Consecutive Cards to Pick Up
h. Fruit into Baskets
i. Find All Anagrams in a String
j. Maximum Average Subarray I
k. Longest Substring with At Least K Repeating Characters
l. Subarray Product Less Than K
m. Repeated DNA Sequences
n. Swap for Longest Repeated Character Substring
o. Get Equal Substrings within Budget
p. Replace the Substring for Balanced String
q. Count Number of Nice Subarrays
r. Maximum Number of Occurrences of a Substring
s. Maximum Points You Can Obtain from Cards
t. Find Two Non-overlapping Sub-arrays Each With Target Sum
16. Divide and Conquer 102
a. Construct Binary Tree from Preorder and Inorder Traversal
b. Construct Binary Tree from Inorder and Postorder Traversal
c. Construct Binary Tree from Preorder and Postorder Traversal
d. Convert Sorted Array to Binary Search Tree
e. Convert Sorted List to Binary Search Tree
f. Maximum Sum Circular Subarray
g. Balance a Binary Search Tree
h. Number of Pairs Satisfying Inequality
i. Number of Ways to Reorder Array to Get Same BST
j. Count of Smaller Numbers after Self
17. Greedy Algorithms 109
a. Task Scheduler
b. Maximum Length of Pair Chain
c. Split Array into Consecutive Subsequences
d. Maximum Swap
e. Valid Parenthesis String
f. Best Time to Buy and Sell Stock with Transaction Fee
g. Monotone Increasing Digits
h. Reorganize String
i. Rabbits in Forest
j. Most Profit Assigning Work
k. Hand of Straights
l. Lemonade Change
4|Page
m. Advantage Shuffle
n. Boats to Save People
o. DI String Match
p. Minimum Increment to Make Array Unique
q. Bag of Tokens
r. Largest Perimeter Triangle
s. String without AAA or BBB
t. Maximum Sum of Array after K Negations
u. Broken Calculator
v. Two City Scheduling
w. Largest Values from Labels
x. Minimum Cost Tree from Leaf Values
y. Balance a Binary Search Tree
z. Longest Happy String
aa. Minimum Cost to Move Chips to the Same Position
bb. Split a String in Balanced Strings
cc. Maximum 69 Number
dd. Assign Cookies
18. Dynamic Programming 124
a. Muzicari
b. Climb the Stairs
c. Edit Distance
d. Decode Ways
e. Maximum Subarray
f. Jump Game
g. Jump Game II
h. Unique Paths
i. Unique Paths II
j. Maximum Path Sum
k. Trapping Rain Water
l. Best Time to Buy and Sell Stock
m. Palindrome Partitioning
n. House Robber
o. Different Ways to Add Parenthesis
p. Ugly Number II
q. Perfect Squares
r. Arithmetic Slices
s. Longest Palindromic Subsequence
t. Coin Change
u. Beautiful Arrangement
v. Min Cost Climbing Stairs
w. Partition Array for Maximum Sum
x. Airplane Seat Assignment Probability
y. Reducing Dishes
19. Backtracking 135
a. Letter Combinations of a Phone Number
b. Combination Sum
c. Combination Sum II
d. Permutations
e. Subsets
f. Gray Code
5|Page
g. Binary Tree Paths
h. Binary Watch
i. Additive Number
j. Matchsticks to Square
k. Path with Maximum Gold
l. Fair Distribution of Cookies
m. Split a String into the Max Number of Unique Substrings
n. Sum of All Subset XOR Totals
o. Find the Punishment Number of an Integer
p. Maximum Split of Positive Even Integers
q. Numbers with Same Consecutive Differences
r. Letter Tile Possibilities
s. What Does It Mean?
t. Non-decreasing Subsequences
20. 0 / 1 Knapsack 147
a. Target Sum
b. Painting the Walls
c. Partition Equal Subset Sum
d. Ones and Zeroes
e. Number of Ways to Earn Points
21. Graph Representation 149
a. Build a Graph
b. Number of Sink Nodes in a Graph
c. Connected Components in a Graph
d. Transpose Graph
e. Counting Triplets
f. Max Area of Island
g. Cheapest Flights within K Stops
h. All Paths from Source to Target
i. Shortest Path with Alternating Colors
j. All Ancestors of a Node in a Directed Acyclic Graph
k. Reorder Routes to Make All Paths Lead to the City Zero
l. Map of Highest Peak
m. Count Sub Islands
n. Find the Town Judge
o. Number of Provinces
p. Find Eventual Safe States
q. Course Schedule
r. Redundant Connection
s. Network Delay Time
t. Is Graph Bipartite
u. Keys and Rooms
v. Seven Bridges of Konigsberg
w. Hamiltonian Cycle
x. Number of Hamiltonian Cycle
22. Graph Traversal 167
a. Minimum Time to Collect All Apples in a Tree
b. Depth First Search
c. Amount of Time for Binary Tree to be Infected
6|Page
23. Shortest Paths 169
a. Travelling Salesman Problem
b. Shortest Paths from Source to all Vertices (Dijkstra's Algorithm)
c. Shortest Cycle in an Undirected Unweighted Graph
d. Count Unique and all Possible Paths in a M x N Matrix
e. Number of Ways to Arrive at Destination
f. Minimum Cost of a Path with Special Roads
g. Shortest Path Visiting All Nodes
h. Shortest Path in an Unweighted Graph
24. Graph Coloring 176
a. Graph Coloring using Greedy Algorithm
b. Coloring a Cycle Graph
c. m Coloring Problem
d. Edge Coloring of a Graph
25. Maximum Flow 179
a. Maximum Students Taking Exam
b. Minimum XOR Sum of Two Arrays
c. Maximum Number of Events that can be Attended
d. Maximum AND Sum of Array
26. Trees 182
a. Maximum Difference between Node and Ancestor
b. Sum of Nodes with Even-Values Grandparent
c. Balance a Binary Search Tree
d. Binary Tree Inorder Traversal
e. Binary Tree Level Order Traversal
f. Maximum Depth of Binary Tree
g. Balanced Binary Tree
h. Minimum Depth of Binary Tree
i. Minimum Depth of Binary Tree
j. Sum Root to Leaf Numbers
27. Minimum Spanning Trees 188
a. Kruskal’s Algorithm
b. Prim’s Algorithm
c. Total Number of Spanning Trees in a Graph
d. Minimum Product Spanning Tree
e. Reverse Delete Algorithm for Minimum Spanning Tree
28. Segment Trees 194
a. Queue Reconstruction by Height
b. Number of Longest Increasing Subsequence
c. Longest Uploaded Prefix
d. Falling Squares
e. My Calendar I
29. Paths and Circuits 197
a. Eulerian Paths
b. Reconstruct Itinerary
c. Cracking the Safe
d. Valid Arrangement of Pairs
e. Find the Shortest Superstring
30. Two Heaps 201
a. Process Tasks Using Servers
b. Median of Two Sorted Arrays
7|Page
c. Find Median from Data Stream
31. Strong Connectivity 203
a. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
b. Minimum Number of Days to Disconnect Island
c. Minimum Edge Weight Equilibrium Queries in a Tree
32. Number Theory 207
a. Count Primes
b. Mirror Reflection
c. Largest Component Size by Common Factor
d. Simplified Fractions
e. The kth Factor of n
f. Number of Different Subsequences GCDs
g. Find Greatest Common Divisor of Array
h. Number of Pairs of Interchangeable Rectangles
i. Replace Non-Coprime Numbers in Array
j. Number of Subarrays with LCM equal to K
33. Combinatorics 212
a. Vowels of All Substrings
b. Find Triangular Sum of an Array
c. Number of Ways to Reach a Position after Exactly k Steps
d. Distribute Candies among Children II
e. Poor Pigs
f. Number of Music Playlists
g. Count All Valid Pickup and Delivery Options
h. Count Sorted Vowel Strings
i. Count Ways to Make Array with Product
j. Minimum Number of Operations to Make String Sorted
34. Probability 218
a. Soup Servings
b. New 21 Game
c. Statistics from a Large Sample
d. Airplane Seat Assignment Probability
e. Implement Rand10() Using Rand7()
f. Path with Maximum Probability
g. Probability of a Two Boxes having the Same Number of Distinct Balls
35. Cycle-Finding 223
a. Detect Cycles in 2D Grid
b. Course Schedule II
c. Shortest Cycle in a Graph
36. Matrices 225
a. Valid Sudoku
b. Rotate Image
c. Spiral Matrix
d. Set Matrix Zeroes
e. Search a 2D Matrix
f. Search a 2D Matrix II
g. Island Perimeter
h. 01 Matrix
i. Reshape the Matrix
j. Score after Flipping Matrix
8|Page
37. Game Theory 231
a. Nim Game
b. Can I Win
c. Predict the Winner
d. Stone Game
e. Cat and Mouse
f. Divisor Game
g. Maximum Number of Coins You Can Get
h. Sum Game
i. Stone Game II
j. Guess the Number Higher or Lower II
38. Geometry 238
a. Rectangle Area
b. Valid Square
c. Largest Triangle Area
d. Rectangle Overlap
e. Surface Area of 3D Shapes
f. Check If It Is a Straight Line
g. Minimum Time Visiting All Points
h. Projection Area of 3D Shapes
i. Minimum Cuts to Divide a Circle
j. Detonate the Maximum Bombs
39. Sweep Line Algorithms 246
a. Intersection Points
b. Closest Pair Problem
c. Convex Hull Problem
40. Network Flow 249
a. Network Delay Time
b. Number of Operations to Make Network Connected
9|Page
Introduction to Competitive Programming
Competitive programming is a sport where contestants solve algorithmic problems within a time limit using
a programming language of their choice. It tests problem-solving skills, knowledge of algorithms, and ability
to write efficient code. This is popular among students, computer science enthusiasts, and professionals
looking to improve their skills. It is also used as a means of recruitment by many companies with many
hosting their own coding competitions. The most popular competitive programming contests are
CodeForces, Google Code Jam, Facebook Hacker Cup, and TopCoder Open. It can help develop skills such
as problem-solving, critical thinking, and efficient coding. These can be valuable in a variety of careers such
as software development, data science, and research. Many companies also use these
programming problems as a way to assess job applicants. As a result, having a strong background in this
can increase your chances of getting hired. However, it’s important to note that competitive programming
alone doesn’t guarantee a successful career; you need to combine it with other relevant skills and
experiences.
Competitive programming combines two topics: the design of algorithms and the implementation of
algorithms. Design of Algorithms: the core of competitive programming is about inventing efficient
algorithms that solve well-defined computational problems. The design of algorithms requires problem-
solving and mathematical skills. Often a solution to a problem is a combination of well-known methods and
new insights. Mathematics plays an important role in competitive programming.
In competitive programming, the solutions to problems are evaluated by testing an implemented algorithm
using a set of test cases. Thus, after coming up with an algorithm that solves the problem, the next step is
to correctly implement it, which requires good programming skills. Competitive programming greatly differs
from traditional software engineering: Programs are short (usually at most some hundreds of lines), they
should be written quickly, and it is not needed to maintain them after the contest.
When solving problems, one should keep in mind that the number of solved problems is not as important
as the quality of the problems. It is tempting to select problems that look nice and easy and solve them,
and skip problems that look hard and tedious. However, the way to really improve one’s skills is to focus on
the latter type of problems.
Another important observation is that most programming contest problems can be solved using simple
and short algorithms, but the difficult part is to invent the algorithm. Competitive programming is not about
learning complex and obscure algorithms by heart, but rather about learning problem solving and ways to
approach difficult problems using simple tools. Finally, some people despise the implementation of
algorithms: It is fun to design algorithms but boring to implement them. However, the ability to quickly and
correctly implement algorithms is an important asset, and this skill can be practiced. It is a bad idea to spend
most of the contest time for writing code and finding bugs, instead of thinking of how to solve problems.
10 | P a g e
Many companies use competitive programming as a means of recruitment. Also, the skills and knowledge
gained through competitive programming can be valuable in technical interviews. It also gives participants
an idea of the type of questions that are likely to be asked during these interviews.
Prizes
Many competitive programming contests offer prizes for the top performers. This can include cash,
scholarships, or even job offers.
1. Searching
11 | P a g e
1.1 Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not,
return the index where it would be if it were inserted in order.
Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
Output: true
Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13
Output: false
12 | P a g e
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k <
nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ...,
nums[k-1]] (0-indexed). For example, [0, 1, 2, 4, 5, 6, 7] might be rotated at pivot index 3 and become [4,
5, 6, 7, 0, 1, 2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is
in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
13 | P a g e
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing
number in the range since it does not appear in nums.
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing
number in the range since it does not appear in nums.
2. Sorting
2.1 Relative Ranks
You are given an integer array score of size n, where score[i] is the score of the ith athlete in a competition.
All the scores are guaranteed to be unique.
The athletes are placed based on their scores, where the 1st place athlete has the highest score,
the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their
rank:
• The 1st place athlete's rank is "Gold Medal".
• The 2nd place athlete's rank is "Silver Medal".
• The 3rd place athlete's rank is "Bronze Medal".
• For the 4th place to the nth place athlete, their rank is their placement number (i.e., the xth place
athlete's rank is "x").
Return an array answer of size n where answer[i] is the rank of the ith athlete.
14 | P a g e
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.
Given an integer array nums, return the length of its longest harmonious subsequence among all its
possible subsequences.
A subsequence of array is a sequence that can be derived from the array by deleting some or no elements
without changing the order of the remaining elements.
Since they are friends, they would like to exchange one candy box each so that after the exchange, they
both have the same total amount of candy. The total amount of candy a person has is the sum of the
number of candies in each box they have.
Return an integer array answer where answer[0] is the number of candies in the box that Alice must
exchange, and answer[1] is the number of candies in the box that Bob must exchange. If there are multiple
answers, you may return any one of them. It is guaranteed that at least one answer exists.
15 | P a g e
Input: nums = [3, 1, 2, 4]
Output: [2, 4, 3, 1]
Explanation: The outputs [4, 2, 3, 1], [2, 4, 1, 3], and [4, 2, 1, 3] would also be accepted.
Input: nums = [0]
Output: [0]
Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the
smallest distance to the largest distance. You may return the answer in any order that satisfies this
condition.
The distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.
Input: costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
16 | P a g e
The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
Input: costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859
Input: costs = [[515, 563], [451, 713], [537, 709], [343, 819], [855, 779], [457, 60], [650, 359], [631, 42]]
Output: 3086
17 | P a g e
3. It repeats until no input elements remain.
The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially
contains only the first element in the list. One element (red) is removed from the input data and inserted
in-place into the sorted list with each iteration.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).
Input: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1, 5, 9, 10, 11, 12, 13, 13, 15], and the 8th smallest number is
13
Input: matrix = [[-5]], k = 1
Output: -5
18 | P a g e
3. Cyclic Sort
3.1 Find All Duplicates in an Array
Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each
integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.
19 | P a g e
3.4 First Missing Positive
Given an unsorted integer array nums, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
4. Topological Sort
4.1 Find All Possible Recipes from Given Supplies
You have information about n different recipes. You are given a string array recipes and a 2D string
array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed
ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes,
i.e., ingredients[i] may contain a string that is in recipes.
You are also given a string array supplies containing all the ingredients that you initially have, and you have
an infinite supply of all of them.
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.
Input: recipes = ["bread"], ingredients = [["yeast", "flour"]], supplies = ["yeast", "flour", "corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
Input: recipes = ["bread", "sandwich"], ingredients = [["yeast", "flour"], ["bread", "meat"]], supplies =
["yeast", "flour", "meat"]
Output: ["bread", "sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
Input: recipes = ["bread", "sandwich", "burger"], ingredients = [["yeast", "flour"], ["bread", "meat"],
["sandwich", "meat", "bread"]], supplies = ["yeast", "flour", "meat"]
Output: ["bread", "sandwich", "burger"]
20 | P a g e
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and
"sandwich".
21 | P a g e
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.
22 | P a g e
Explanation: The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2.
The length of this cycle is 3, so 3 is returned.
• The number abovei should appear in a row that is strictly above the row at which the
number belowi appears for all i from 0 to n - 1.
• The number lefti should appear in a column that is strictly left of the column at which the
number righti appears for all i from 0 to m - 1.
Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.
Input: k = 3, rowConditions = [[1, 2], [3, 2]], colConditions = [[2, 1], [3, 2]]
Output: [[3, 0, 0], [0, 0, 1], [0, 2, 0]]
23 | P a g e
Explanation: The diagram above shows a valid example of a matrix that satisfies all the conditions.
The row conditions are the following:
- Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix.
- Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix.
The column conditions are the following:
- Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix.
- Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix.
Note that there may be multiple correct answers.
Input: k = 3, rowConditions = [[1, 2], [2, 3], [3, 1], [2, 3]], colConditions = [[2, 1]]
Output: []
Explanation: From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be
above 1 to be satisfied.
No matrix can satisfy all the conditions, so we return the empty matrix.
24 | P a g e
Input: prevRoom = [-1, 0, 0, 1, 2]
Output: 6
Explanation:
The 6 ways are:
0→1→3→2→4
0→2→4→1→3
0→1→2→3→4
0→1→2→4→3
0→2→1→3→4
0→2→1→4→3
5. Strings
5.1 Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
• countAndSay(1) = "1"
• countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then
converted into a different digit string.
25 | P a g e
To determine how you "say" a digit string, split it into the minimal number of substrings such that each
substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the
digit. Finally, concatenate every said digit.
For example, the saying and conversion for digit string "3322251":
Given a positive integer n, return the nth term of the count-and-say sequence.
Input: n = 1
Output: "1"
Explanation: This is the base case.
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
26 | P a g e
• For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses,
but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by
inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP
addresses in any order.
Input: s = "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Input: s = "0000"
Output: ["0.0.0.0"]
Input: s = "101023"
Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...
27 | P a g e
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.
Input: s1 = "", s2 = "", s3 = ""
Output: true
28 | P a g e
• The number of "bulls", which are digits in the guess that are in the correct position.
• The number of "cows", which are digits in the guess that are in your secret number but are located
in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such
that they become bulls.
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.
The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note
that both secret and guess may contain duplicate digits.
Input: s = "bcabc"
Output: "abc"
Input: s = "cbacdcbc"
Output: "acdb"
30 | P a g e
• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.
You must implement a solution with O(1) time complexity for each function.
31 | P a g e
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Notes:
• You must use only standard operations of a stack, which means only push to top, peek/pop from
top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack
using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
32 | P a g e
6.4 Remove Duplicate Letters
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make
sure your result is the smallest in lexicographical order among all possible results.
Input: s = "bcabc"
Output: "abc"
Input: s = "cbacdcbc"
Output: "acdb"
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#",
where '#' represents a null node.
Given a string of comma-separated values preorder, return true if it is a correct preorder traversal
serialization of a binary tree.
It is guaranteed that each comma-separated value in the string must be either an integer or a
character '#' representing null pointer.
You may assume that the input format is always valid.
• For example, it could never contain two consecutive commas, such as "1,,3".
33 | P a g e
6.6 Mini Parser
Given a string s represents the serialization of a nested list, implement a parser to deserialize it and
return the deserialized NestedInteger.
Each element is either an integer or a list whose elements may also be integers or other lists.
Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.
Input: s = "[123, [456, [789]]]"
Output: [123, [456, [789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i. An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Input: s = "3[a2[c]]"
Output: "accaccacc"
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
34 | P a g e
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next
greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query
is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described
above.
• An integer x.
• '+'.
• Record a new score that is the sum of the previous two scores.
• 'D'.
• 'C'.
Return the sum of all the scores on the record after applying all the operations.
The test cases are generated such that the answer and all intermediate calculations fit in a 32-bit integer
and that all operations are valid.
36 | P a g e
Input: nums = [3, 2, 1, 6, 0, 5]
Output: [6, 3, 5, null, 2, 0, null, null, 1]
Explanation: The recursive calls are as follow:
- The largest value in [3, 2, 1, 6, 0, 5] is 6. Left prefix is [3, 2, 1] and right suffix is [0,5].
- The largest value in [3, 2, 1] is 3. Left prefix is [] and right suffix is [2, 1].
- Empty array, so no child.
- The largest value in [2, 1] is 2. Left prefix is [] and right suffix is [1].
- Empty array, so no child.
- Only one element, so child is a node with value 1.
- The largest value in [0, 5] is 5. Left prefix is [0] and right suffix is [].
- Only one element, so child is a node with value 0.
- Empty array, so no child.
37 | P a g e
6.11 Daily Temperatures
Given an array of integers temperatures represents the daily temperatures, return an array answer such
that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there
is no future day for which this is possible, keep answer[i] == 0 instead.
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Input: temperatures = [30, 40, 50, 60]
Output: [1, 1, 1, 0]
Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]
Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf
node. It is guaranteed this sum fits into a 32-bit integer.
A node is a leaf if and only if it has zero children.
38 | P a g e
Input: arr = [6, 2, 4]
Output: 32
Explanation: There are two possible trees shown.
The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.
You also have a stream of the integers in the range [1, n].
Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target.
You should follow the following rules:
• If the stream of the integers is not empty, pick the next integer from the stream and push it to the
top of the stack.
• If the stack is not empty, pop the integer at the top of the stack.
• If, at any moment, the elements in the stack (from the bottom to the top) are equal to target, do
not read new integers from the stream and do not do more operations on the stack.
Return the stack operations needed to build target following the mentioned rules. If there are multiple valid
answers, return any of them.
39 | P a g e
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1, 2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1, 3].
Input: target = [1, 2, 3], n = 3
Output: ["Push", "Push", "Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1, 2].
Read 3 from the stream and push it to the stack. s = [1, 2, 3].
Input: target = [1, 2], n = 4
Output: ["Push", "Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1, 2].
Since the stack (from the bottom to the top) is equal to target, we stop the stack operations.
The answers that read integer 3 from the stream are not accepted.
40 | P a g e
6.16 Number of Visible People in a Queue
There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are
given an array heights of distinct integers where heights[i] represents the height of the ith person.
A person can see another person to their right in the queue if everybody in between is shorter than both
of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) >
max(heights[i+1], heights[i+2], ..., heights[j-1]).
Return an array answer of length n where answer[i] is the number of people the ith person can see to their
right in the queue.
41 | P a g e
Input: n = 6, delay = 2, forget = 4
Output: 5
Explanation:
Day 1: Suppose the first person is named A. (1 person)
Day 2: A is the only person who knows the secret. (1 person)
Day 3: A shares the secret with a new person, B. (2 people)
Day 4: A shares the secret with a new person, C. (3 people)
Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people)
Day 6: B shares the secret with E, and C shares the secret with F. (5 people)
Input: n = 4, delay = 1, forget = 3
Output: 6
Explanation:
Day 1: The first person is named A. (1 person)
Day 2: A shares the secret with B. (2 people)
Day 3: A and B share the secret with 2 new people, C and D. (4 people)
Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)
1. Take the top card of the deck, reveal it, and take it out of the deck.
2. If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
3. If there are still unrevealed cards, go back to step 1. Otherwise, stop.
Return an ordering of the deck that would reveal the cards in increasing order.
Note that the first entry in the answer is considered to be the top of the deck.
Given the number of friends, n, and an integer k, return the winner of the game.
Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
43 | P a g e
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.
Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.
44 | P a g e
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear(); // return 2
myCircularDeque.isFull(); // return True
myCircularDeque.deleteLast(); // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront(); // return 4
45 | P a g e
7.3 Palindrome Linked List
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
46 | P a g e
7.5 Convert Binary Number in a Linked List to Integer
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either
0 or 1. The linked list holds the binary representation of a number.
Return the decimal value of the number in the linked list. The most significant bit is at the head of the linked
list.
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected
node.
• listA - The first linked list.
• listB - The second linked list.
• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected
node.
• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected
node.
The judge will then create the linked structure based on these inputs and pass the two
heads, headA and headB to your program. If you correctly return the intersected node, then your solution
will be accepted.
47 | P a g e
Input: intersectVal = 8, listA = [4, 1, 8, 4, 5], listB = [5, 6, 1, 8, 4, 5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4, 1, 8, 4, 5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes
before the intersected node in A; There are 3 nodes before the intersected node in B.
Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2 nd node in A
and 3rd node in B) are different node references. In other words, they point to two different locations in
memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location
in memory.
Input: intersectVal = 2, listA = [1, 9, 1, 2, 4], listB = [3, 2, 4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1, 9, 1, 2, 4]. From the head of B, it reads as [3, 2, 4]. There are 3 nodes
before the intersected node in A; There are 1 node before the intersected node in B.
48 | P a g e
7.7 Delete Node in a Linked List
There is a singly-linked list head and we want to delete a node node in it.
You are given the node to be deleted node. You will not be given access to the first node of head.
All the values of the linked list are unique, and it is guaranteed that the given node node is not the last
node in the linked list.
Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We
mean:
• The value of the given node should not exist in the linked list.
• The number of nodes in the linked list should decrease by one.
• All the values before node should be in the same order.
• All the values after node should be in the same order.
Custom testing:
• For the input, you should provide the entire linked list head and the node to be
given node. node should not be the last node of the list and should be an actual node in the list.
• We will build the linked list and pass the node to your function.
• The output will be the entire list after calling your function.
50 | P a g e
• void follow(int followerId, int followeeId) The user with ID followerId started following the user with
ID followeeId.
• void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user
with ID followeeId.
Input
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]
Output
[null, null, [5], null, null, [6, 5], null, [5]]
Explanation
Twitter twitter = new Twitter();
twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5).
twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5]. return [5]
twitter.follow(1, 2); // User 1 follows user 2.
twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6).
twitter.getNewsFeed(1); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6
should precede tweet id 5 because it is posted after tweet id 5.
twitter.unfollow(1, 2); // User 1 unfollows user 2.
twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no
longer following user 2.
• Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the
list should be equally likely to be chosen.
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
51 | P a g e
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of
returning.
53 | P a g e
Build the result list and return its head.
• For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are
the only nodes with twins for n = 4.
The twin sum is defined as the sum of a node and its twin.
Given the head of a linked list with even length, return the maximum twin sum of the linked list.
54 | P a g e
Input: head = [5, 4, 2, 1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.
56 | P a g e
Input: head = [18, 6, 10, 3]
Output: [18, 6, 6, 2, 10, 1, 3]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after
inserting the new nodes (nodes in blue are the inserted nodes).
- We insert the greatest common divisor of 18 and 6 = 6 between the 1 st and the 2nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2 nd and the 3rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3 rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.
57 | P a g e
Input: head = [0, 1, 2], k = 4
Output: [2, 0, 1]
8. Bit Manipulation
8.1 Raising Bacteria
You are a lover of bacteria. You want to raise some bacteria in a box. Initially, the box is empty. Each morning,
you can put any number of bacteria into the box. And each night, every bacterium in the box will split into
two bacteria. You hope to see exactly x bacteria in the box at some moment. What is the minimum number
of bacteria you need to put into the box across those days?
58 | P a g e
Input: 5
Output: 2
Explanation: we can add one bacterium in the box in the first day morning and at the third morning there
will be 4 bacteria in the box. Now we put one more resulting 5 in the box. We added 2 bacteria in the
process so the answer is 2.
59 | P a g e
Let n is stored using 8 bits. Left rotation of n = 11100101 by 3 makes n = 00101111 (Left shifted by 3 and
first 3 bits are put back in last). If n is stored using 16 bits or 32 bits then left rotation of n (000…11100101)
becomes 00…0011100101000.
Right rotation of n = 11100101 by 3 makes n = 10111100 (Right shifted by 3 and last 3 bits are put back in
first) if n is stored using 8 bits. If n is stored using 16 bits or 32 bits then right rotation of n (000…11100101)
by 3 becomes 101000…0011100.
Input: n = 16
Output:
Left rotation of 16 by 2 is 64
Right rotation of 16 by 2 is 4
60 | P a g e
• 2 is even; divide by 2 and obtain 1.
• 1 is odd; subtract 1 and obtain 0.
Input: num = 8
Output: 4
Explanation:
• 8 is even; divide by 2 and obtain 4.
• 4 is even; divide by 2 and obtain 2.
• 2 is even; divide by 2 and obtain 1.
• 1 is odd; subtract 1 and obtain 0.
Input: num = 123
Output: 12
Example: for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros
not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right
to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.
Given two integers start and goal, return the minimum number of bit flips to convert start to goal.
Input: start = 10, goal = 7
Output: 3
Explanation:
The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.
Input: start = 3, goal = 4
Output: 3
Explanation:
• The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4
in 3 steps:
• - Flip the first bit from the right: 011 -> 010.
• - Flip the second bit from the right: 010 -> 000.
• - Flip the third bit from the right: 000 -> 100.
9. Heaps
61 | P a g e
9.1 Kth Largest Element in an Array
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.
Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to
another 4-directionally adjacent square if and only if the elevation of both squares individually are at
most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the
grid during your swim.
Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left
square (0, 0).
62 | P a g e
Input: grid = [[0, 2], [1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t =
0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
Input: grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
Output: 16
Explanation: The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
63 | P a g e
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
10. HashMap
10.1 The Skyline Problem
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed
from a distance. Given the locations and heights of all the buildings, return the skyline formed by these
buildings collectively.
The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti,
heighti]:
You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form [[x1,
y1], [x2, y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last
point in the list, which always has a y-coordinate 0 and is used to mark the skyline's termination where the
rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the
skyline's contour.
Note: There must be no consecutive horizontal lines of equal height in the output skyline. For
instance, [...,[2 3], [4 5], [7 5], [11 5], [12 7],...] is not acceptable; the three lines of height 5 should be
merged into one in the final output as such: [...,[2 3], [4 5], [12 7],...]
Input: buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
Output: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points
in the output list.
Input: buildings = [[0, 2, 3], [2, 5, 3]]
Output: [[0, 3], [5, 0]]
65 | P a g e
10.2 Sliding Window Median
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle
value. So the median is the mean of the two middle values.
You are given an integer array nums and an integer k. There is a sliding window of size k which is moving
from the very left of the array to the very right. You can only see the k numbers in the window. Each time
the sliding window moves right by one position.
Return the median array for each window in the original array. Answers within 10-5 of the actual value will
be accepted.
Input: nums = [[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]
Output: [20, 24]
Explanation:
List 1: [4, 10, 15, 24, 26], 24 is in range [20, 24].
List 2: [0, 9, 12, 20], 20 is in range [20, 24].
List 3: [5, 18, 22, 30], 22 is in range [20, 24].
66 | P a g e
Example 2:
Input: nums = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Output: [1, 1]
In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a
cell with a tree, you can choose whether to cut it off.
You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell
becomes 1 (an empty cell).
Starting from the point (0, 0), return the minimum steps you need to walk to cut off all the trees. If you
cannot cut off all the trees, return -1.
Note: The input is generated such that no two trees have the same height, and there is at least one tree
needs to be cut off.
67 | P a g e
Input: forest = [[1, 2, 3], [0, 0, 0], [7, 6, 5]]
Output: -1
Explanation: The trees in the bottom row cannot be accessed as the middle row is blocked.
Input: forest = [[2, 3, 4], [0, 0, 5], [8, 7, 6]]
Output: 6
Explanation: You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.
• |a - x| < |b - x|, or
• |a - x| == |b - x| and a < b
1. Every worker in the paid group should be paid in the ratio of their quality compared to other
workers in the paid group.
2. Every worker in the paid group must be paid at least their minimum wage expectation.
Given the integer k, return the least amount of money needed to form a paid group satisfying the above
conditions. Answers within 10-5 of the actual answer will be accepted.
68 | P a g e
Input: quality = [10, 20, 5], wage = [70, 50, 30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.
Input: quality = [3, 1, 10, 10, 1], wage = [4, 8, 2, 2, 7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.
• DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks capacity.
• void push(int val) Pushes the given integer val into the leftmost stack with a size less
than capacity.
• int pop() Returns the value at the top of the rightmost non-empty stack and removes it from that
stack, and returns -1 if all the stacks are empty.
• int popAtStack(int index) Returns the value at the top of the stack with the given index index and
removes it from that stack or returns -1 if the stack with that given index is empty.
Input: ["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack",
"popAtStack", "pop", "pop", "pop", "pop", "pop"]
[[2], [1], [2], [3], [4], [5], [0], [20], [21], [0], [2], [], [], [], [], []]
Output: [null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]
Explanation:
DinnerPlates D = DinnerPlates(2); // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5); // The stacks are now: 2 4
1 3 5
﹈﹈﹈
﹈﹈﹈
﹈﹈﹈
70 | P a g e
D.push(21); // The stacks are now: 20 4 21
1 3 5
﹈﹈﹈
﹈﹈﹈
﹈﹈﹈
﹈﹈
﹈﹈
71 | P a g e
Input: apples = [3, 0, 0, 0, 0, 2], days = [3, 0, 0, 0, 0, 2]
Output: 5
Explanation: You can eat 5 apples:
- On the first to the third day you eat apples that grew on the first day.
- Do nothing on the fourth and fifth days.
- On the sixth and seventh days you eat apples that grew on the sixth day.
72 | P a g e
Your task is to make s a palindrome with the minimum number of operations possible. If there
are multiple palindromes that can be made using the minimum number of operations, make
the lexicographically smallest one.
A string a is lexicographically smaller than a string b (of the same length) if in the first position
where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter
in b.
Return the resulting palindrome string.
Input: s = "egcfe"
Output: "efcfe"
Explanation: The minimum number of operations to make "egcfe" a palindrome is 1, and the
lexicographically smallest palindrome string we can get by modifying one character is "efcfe", by changing
'g'.
Input: s = "abcd"
Output: "abba"
Explanation: The minimum number of operations to make "abcd" a palindrome is 2, and the
lexicographically smallest palindrome string we can get by modifying two characters is "abba".
Input: s = "seven"
Output: "neven"
Explanation: The minimum number of operations to make "seven" a palindrome is 1, and the
lexicographically smallest palindrome string we can get by modifying one character is "neven".
73 | P a g e
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.
Input: nums1 = [[2, 4], [3, 6], [5, 5]], nums2 = [[1, 3], [4, 3]]
Output: [[1, 3], [2, 4], [3, 6], [4, 3], [5, 5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.
74 | P a g e
We pick the first element, 14, and the last element, 8.
Their concatenation is 148, and we add it to the concatenation value, so it becomes equal to 660.
Then we delete them from the nums, so nums becomes equal to [13].
- In the third operation:
nums has only one element, so we pick 13 and add it to the concatenation value, so it becomes equal to
673.
Then we delete it from nums, so nums become empty.
Since the concatenation value is 673 so the answer is 673.
75 | P a g e
It can be proven that 2 is the maximum number of matchings that can be formed.
Input: players = [1, 1, 1], trainers = [10]
Output: 1
Explanation:
The trainer can be matched with any of the 3 players.
Each player can only be matched with one trainer, so the maximum answer is 1.
Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.
Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.
76 | P a g e
Input: nums = [4, 5, 6, 7, 8, 9], diff = 2
Output: 2
Explanation:
(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2.
(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.
77 | P a g e
Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".
Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.
79 | P a g e
|8-8|=0 <= d=2
Input: arr1 = [1, 4, 2, 3], arr2 = [-4, -3, 6, 10, 20, 30], d = 3
Output: 2
Example 3:
Input: arr1 = [2, 1, 100, 3], arr2 = [-5, -2, 10, -3, 7], d = 6
Output: 1
80 | P a g e
• For example, inverting [0, 1, 1] results in [1, 0, 0].
81 | P a g e
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and
0's.
82 | P a g e
Output: 2
Input: nums = [3, 1, 3, 4, 2]
Output: 3
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Input: n = 2
Output: false
• NumArray(int[] nums) Initializes the object with the integer array nums.
• void update(int index, int val) Updates the value of nums[index] to be val.
• int sumRange(int left, int right) Returns the sum of the elements of nums between
indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
83 | P a g e
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output: [null, 9, null, 8]
Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
1. Calculate the sum of the elements of nums between indices left and right inclusive where left <=
right.
• NumArray(int[] nums) Initializes the object with the integer array nums.
• int sumRange(int left, int right) Returns the sum of the elements of nums between
indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
• RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer
array arr.
• int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].
A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that
contains the elements of nums between indices left and right (inclusive).
84 | P a g e
Input: ["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output: [null, 1, 2]
Explanation:
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4]
rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.
85 | P a g e
Input: nums = [-2, 5, -1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0, 0], [2, 2], and [0, 2] and their respective sums are: -2, -1, 2.
Input: nums = [0], lower = 0, upper = 0
Output: 1
13. Trie
13.1 Implement Trie (Prefix Tree)
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys
in a dataset of strings. There are various applications of this data structure, such as autocomplete and
spellchecker.
Implement the Trie class:
Input:
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[], ["bad"], ["dad"], ["mad"], ["pad"], ["bad"], [".ad"], ["b.."]]
Output:
[null, null, null, null, false, true, true, true]
Explanation:
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True
Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Input: n = 2
Output: [1,2]
87 | P a g e
Input: dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Input: dictionary = ["a", "b", "c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
88 | P a g e
Input: ["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output: [null, null, 3, null, 5]
Explanation:
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
• WordFilter(string[] words) Initializes the object with the words in the dictionary.
• f(string pref, string suff) Returns the index of the word in the dictionary, which has the
prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If
there is no such word in the dictionary, return -1.
89 | P a g e
Explanation:
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".
• For example, "/leetcode" and "/leetcode/problems" are valid paths while an empty string
and "/" are not.
90 | P a g e
Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes,
return the second middle node.
91 | P a g e
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
While traversing the linked list one of these things will occur-
• The Fast pointer may reach the end (NULL) this shows that there is no loop in the linked list.
• The Fast pointer again catches the slow pointer at some time therefore a loop exists in the linked
list.
92 | P a g e
Input: head = [1, 2, 3, 4, 5], n = 2
Output: [1, 2, 3, 5]
Input: head = [1], n = 1
Output: []
Input: head = [1, 2], n = 1
Output: [1]
Output: 2
93 | P a g e
- "30" from "430043": 30 is not a divisor of 430043.
- "00" from "430043": 0 is not a divisor of 430043.
- "04" from "430043": 4 is not a divisor of 430043.
- "43" from "430043": 43 is a divisor of 430043.
Therefore, the k-beauty is 2.
Input: s = "YazaAay"
Output: "aAa"
Explanation: "aAa" is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a'
appear.
"aAa" is the longest nice substring.
Input: s = "Bb"
Output: "Bb"
Explanation: "Bb" is a nice string because both 'B' and 'b' appear. The whole string is a substring.
Input: s = "c"
Output: ""
94 | P a g e
Explanation: There are no nice substrings.
Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".
The only good substring of length 3 is "xyz".
Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".
95 | P a g e
- [9, 4, 1, 7]. The difference between the highest and lowest score is 7 - 1 = 6.
The minimum possible difference is 2.
96 | P a g e
15.8 Fruit into Baskets
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are
represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on
the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the
start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
97 | P a g e
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
98 | P a g e
15.13 Repeated DNA Sequences
The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.
• For example, "ACGAATTCCG" is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.
Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that
occur more than once in a DNA molecule. You may return the answer in any order.
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
99 | P a g e
Return the maximum length of a substring of s that can be changed to be the same as the corresponding
substring of t with a cost less than or equal to maxCost. If there is no substring from s that can be changed
to its corresponding substring from t, return 0.
Input: s = "QWER"
Output: 0
Explanation: s is already balanced.
Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.
Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER".
100 | P a g e
Input: nums = [1, 1, 2, 1, 1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1, 1, 2, 1] and [1, 2, 1, 1].
Input: nums = [2, 4, 6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.
Input: nums = [2, 2, 2, 1, 2, 2, 1, 2, 2, 2], k = 2
Output: 16
Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
102 | P a g e
Output: [3, 9, 20, null, null, 15, 7]
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: [3, 9, 20, null, null, 15, 7]
Input: inorder = [-1], postorder = [-1]
Output: [-1]
103 | P a g e
Input: preorder = [1, 2, 4, 5, 3, 6, 7], postorder = [4, 5, 2, 6, 7, 3, 1]
Output: [1, 2, 3, 4, 5, 6, 7]
Input: preorder = [1], postorder = [1]
Output: [1]
104 | P a g e
Input: nums = [1, 3]
Output: [3, 1]
Explanation: [1, null, 3] and [3, 1] are both height-balanced BSTs.
105 | P a g e
A circular array means the end of the array connects to the beginning of the array. Formally, the next
element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
A subarray may only include each element of the fixed buffer nums at most once. Formally, for a
subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
106 | P a g e
Input: root = [2, 1, 3]
Output: [2, 1, 3]
• For example, given nums = [2, 1, 3], we will have 2 as the root, 1 as a left child, and 3 as a right child.
The array [2, 3, 1] also yields the same BST but [3, 2,1] yields a different BST.
Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed
from nums.
107 | P a g e
Since the answer may be very large, return it modulo 109 + 7.
108 | P a g e
16.10 Count of Smaller Numbers after Self
Given an integer array nums, return an integer array counts where counts[i] is the number of smaller
elements to the right of nums[i].
110 | P a g e
[1, 2, 3, 3, 4, 4, 5, 5] --> 1, 2, 3, 4, 5
[1, 2, 3, 3, 4, 4, 5, 5] --> 3, 4, 5
Input: nums = [1, 2, 3, 4, 4, 5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.
Input: s = "()"
Output: true
Input: s = "(*)"
Output: true
Input: s = "(*))"
Output: true
17.6 Best Time to Buy and Sell Stock with Transaction Fee
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an
integer fee representing a transaction fee.
111 | P a g e
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you
need to pay the transaction fee for each transaction.
Note:
• You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you
buy again).
• The transaction fee is only charged once for each stock purchase and sale.
113 | P a g e
Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize,
return true if she can rearrange the cards, or false otherwise.
Input: hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]
Example 2:
Input: hand = [1, 2, 3, 4, 5], groupSize = 4
Output: false
Explanation: Alice's hand cannot be rearranged into groups of 4.
114 | P a g e
Input: nums1 = [2, 7, 11, 15], nums2 = [1, 10, 4, 11]
Output: [2, 11, 7, 15]
Input: nums1 = [12, 24, 8, 32], nums2 = [13, 25, 32, 11]
Output: [24, 32, 8, 12]
116 | P a g e
Input: nums = [2, 1, 2]
Output: 5
Explanation: You can form a triangle with three side lengths: 1, 2, and 2.
Input: nums = [1, 2, 1, 10]
Output: 0
Explanation:
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.
117 | P a g e
17.21 Broken Calculator
There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:
• multiply the number on display by 2, or
• subtract 1 from the number on display.
Given two integers startValue and target, return the minimum number of operations needed to
display target on the calculator.
Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.
Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.
Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.
Input: costs = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
Input: costs = [[259, 770], [448, 54], [926, 667], [184, 139], [840, 118], [577, 469]]
Output: 1859
Input: costs = [[515, 563], [451, 713], [537, 709], [343, 819], [855, 779], [457, 60], [650, 359], [631, 42]]
Output: 3086
118 | P a g e
There is a set of n items. You are given two integer arrays values and labels where the value and the label
of the ith element are values[i] and labels[i] respectively. You are also given two
integers numWanted and useLimit.
Choose a subset s of the n elements such that:
• The size of the subset s is less than or equal to numWanted.
• There are at most useLimit items with the same label in s.
The score of a subset is the sum of the values in the subset.
Return the maximum score of a subset s.
119 | P a g e
Input: arr = [4, 11]
Output: 44
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.
121 | P a g e
Input: position = [2, 2, 2, 3, 3]
Output: 2
Explanation: We can move the two chips at position 3 to position 2. Each move has cost = 1. The total cost
= 2.
Input: position = [1, 1000000000]
Output: 1
122 | P a g e
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.
Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.
Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.
Additionally, during the concert, each of the musicians at one point takes a break. If three or more of them
are on a break at the same time, they start stirring trouble in town and the rest of the group start panicking
and playing the wrong chords.
123 | P a g e
The concert will be T minutes long, during which each of the N members will take a break. The length of
the break is known for each member.
Help the organizer of the concert by writing a program that determines how to schedule the breaks of the
members so that, at any given moment, at most two are absent from the stage. All breaks must
be entirely during the concert.
Input
The first line of input contains the integers T and N (1≤T≤5000, 1≤N≤500), the length of the concert in
minutes and the number of musicians in the group.
The next line contains N integers (each between 1 and T inclusive) separated by single spaces, the length
of the break in minutes for each member.
Note: The input data will be such that a solution, although not necessarily unique, will always exist.
Output
For each musician output one integer, the number of minutes the musician will spend on stage before going
on the break. Output the musicians in the same order they were given in the input.
Sample Input 1:
83
444
Sample Output 1:
024
Sample Input 2:
10 5
75123
Sample Output 2:
33900
124 | P a g e
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
...
To decode an encoded message, all the digits must be grouped then mapped back into letters using the
reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different
from "06".
125 | P a g e
Given a string s containing only digits, return the number of ways to decode it.
The test cases are generated so that the answer fits in a 32-bit integer.
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
126 | P a g e
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you
are at nums[i], you can jump to any nums[i + j] where:
• 0 <= j <= nums[i] and
• i+j<n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can
reach nums[n - 1].
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1,
then 3 steps to the last index.
Input: nums = [2, 3, 0, 1, 4]
Output: 2
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
127 | P a g e
You are given an m x n integer array grid. There is a robot initially located at the top-left
corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The
robot can only move either down or right at any point in time.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot
include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
128 | P a g e
Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1, 2, 3], [4, 5, 6]]
Output: 12
129 | P a g e
18.13 Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible
palindrome partitioning of s.
Input: s = "aab"
Output: [["a", "a", "b"], ["aa", "b"]]
Example 2:
Input: s = "a"
Output: [["a"]]
130 | P a g e
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
131 | P a g e
Output: 0
133 | P a g e
18.23 Partition Array for Maximum Sum
Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After
partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits
in a 32-bit integer.
Input: arr = [1, 15, 7, 9, 2, 5, 10], k = 3
Output: 84
Explanation: arr becomes [15, 15, 15, 9, 10, 10, 10]
Example 2:
Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83
Example 3:
Input: arr = [1], k = 1
Output: 1
134 | P a g e
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be
equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.
Input: satisfaction = [4, 3, 2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.
135 | P a g e
Given an array of distinct integers candidates and a target integer target, return a list of all unique
combinations of candidates where the chosen numbers sum to target. You may return the combinations
in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are
unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less
than 150 combinations for the given input.
136 | P a g e
19.4 Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer
in any order.
19.5 Subsets
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
138 | P a g e
Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM),
return all possible times the watch could represent. You may return the answer in any order.
The hour must not contain a leading zero.
• For example, "01:00" is not valid. It should be "1:00".
The minute must consist of two digits and may contain a leading zero.
• For example, "10:2" is not valid. It should be "10:02".
Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
Input: turnedOn = 9
Output: []
139 | P a g e
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
Input: "199100199"
Output: true
Explanation:
The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
140 | P a g e
Output: 24
Explanation:
[[0, 6, 0],
[5, 8, 7],
[0, 9, 0]]
Path to get the maximum gold, 9 -> 8 -> 7.
Input: grid = [[1, 0, 7], [2, 0, 6], [3, 4, 5], [0, 3, 0], [9, 0, 20]]
Output: 28
Explanation:
[[1, 0, 7],
[2, 0, 6],
[3, 4, 5],
[0, 3, 0],
[9, 0, 20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
142 | P a g e
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5, 1] has an XOR total of 5 XOR 1 = 4.
- [5, 6] has an XOR total of 5 XOR 6 = 3.
- [1, 6] has an XOR total of 1 XOR 6 = 7.
- [5, 1, 6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
Input: nums = [3, 4, 5, 6, 7, 8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.
Input: n = 10
Output: 182
Explanation: There are exactly 3 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
Hence, the punishment number of 10 is 1 + 81 + 100 = 182
Input: n = 37
Output: 1478
Explanation: There are exactly 4 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1.
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
- 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6.
Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478
143 | P a g e
You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even
integers.
• For example, given finalSum = 12, the following splits are valid (unique positive even integers
summing up to finalSum): (12), (2 + 10), (2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains
the maximum number of integers. Note that finalSum cannot be split into (2 + 2 + 4 + 4) as all the
numbers should be unique.
Return a list of integers that represent a valid split containing a maximum number of integers. If no valid
split exists for finalSum, return an empty list. You may return the integers in any order.
Input: finalSum = 12
Output: [2, 4, 6]
Explanation: The following are valid splits: (12), (2 + 10), (2 + 4 + 6), and (4 + 8).
(2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2, 4, 6].
Note that [2, 6, 4], [6, 2, 4], etc. are also accepted.
Input: finalSum = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.
Input: finalSum = 28
Output: [6, 8, 2, 12]
Explanation: The following are valid splits: (2 + 26), (6 + 8 + 2 + 12), and (4 + 24).
(6 + 8 + 2 + 12) has the maximum number of integers, which is 4. Thus, we return [6, 8, 2,12].
Note that [10, 2, 4, 12], [6, 2, 4, 16], etc. are also accepted.
Input: n = 3, k = 7
Explanation: Note that 070 is not a valid number, because it has leading zeroes.
Input: n = 2, k = 1
Output: [10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98]
144 | P a g e
Return the number of possible non-empty sequences of letters you can make using the letters printed on
those tiles.
Input: The first line contains an integer N and a word W, indicating the number of words in the dictionary
and the family name respectively. The following N lines contain the dictionary. Each dictionary line starts
with the dictionary word followed by an integer representing the number of meanings of the word.
Output: Output the number of possible meanings Bob’s family name can have. As this number can be
very large, output it modulo 1000000007.
Input:
5 heimark
hei 2
mark 2
heim 1
ark 2
heima 1
Output: 6
145 | P a g e
Input: nums = [4, 6, 7, 7]
Output: [[4, 6], [4, 6, 7], [4, 6, 7, 7], [4, 7], [4, 7, 7], [6, 7], [6, 7, 7], [7, 7]]
Input: nums = [4, 4, 3, 2, 1]
Output: [[4, 4]]
• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them
to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.
• A paid painter that paints the ith wall in time[i] units of time and takes cost[i] units of money.
• A free painter that paints any wall in 1 unit of time at a cost of 0. But the free painter can only be
used if the paid painter is already occupied.
146 | P a g e
Return the minimum amount of money required to paint the n walls.
147 | P a g e
20.5 Number of Ways to Earn Points
There is a test that has n types of questions. You are given an integer target and a 0-indexed 2D integer
array types where types[i] = [counti, marksi] indicates that there are counti questions of the ith type, and
each one of them is worth marksi points.
Return the number of ways you can earn exactly target points in the exam. Since the answer may be too
large, return it modulo 109 + 7.
• For example, if there are 3 questions of the same type, then solving the 1st and 2nd questions is the
same as solving the 1st and 3rd questions, or the 2nd and 3rd questions.
148 | P a g e
• Its degree is less than or equal to 1.
• It's a cut-vertex.
Note:
• The graph must be simple.
• Loops and multiple edges are not allowed.
Input: First line: n
Output: Print Yes if it is an unconnected graph. Otherwise, print No.
Sample Input Sample Output
3 No
Constraints: 1 ≤ n ≤ 100
Explanation: There is only one graph with the number of edges equal to the number of vertices (triangle)
which is connected.
Output: 3
The idea is to iterate through all the edges. And for each edge, mark the source node from which the edge
emerged out. Now, for each node check if it is marked or not. And count the unmarked nodes.
Algorithm:
1. Make any array A[] of size equal to the number of nodes and initialize to 1.
3. Now traverse whole array A[] and count number of unmarked nodes.
149 | P a g e
21.3 Connected Components in a Graph
Given n, i.e. total number of nodes in an undirected graph numbered from 1 to n and an integer e, i.e. total
number of edges in the graph. Calculate the total number of connected components in the graph. A
connected component is a set of vertices in a graph that are linked to each other by paths.
Input: First line of input line contains two integers’ n and e. Next e line will contain two integers u and v
meaning that node u and node v are connected to each other in undirected fashion.
Output: For each input graph print an integer x denoting total number of connected components.
Constraints: All the input values are well within the integer range.
Explanation: We traverse the adjacency list and as we find a vertex v in the adjacency list of vertex u which
indicates an edge from u to v in main graph, we just add an edge from v to u in the transpose graph i.e.
add u in the adjacency list of vertex v of the new graph. Thus traversing lists of all vertices of main graph
we can get the transpose graph.
150 | P a g e
21.5 Counting Triplets
You are given an undirected, complete graph G that contains N vertices. Each edge is colored in either
white or black. You are required to determine the number of triplets (i, j, k) (1 ≤ i < j < k ≤ N) of vertices
such that the edges (i, j), (j, k), (i, k) are of the same color.
Input:
(i+1)th line: Two integers – ui and vi (1 ≤ ui, vi ≤ N) denoting that the edge (ui, vi) is white in color.
Note: The conditions (ui, vi) ≠ (uj, vj) and (ui, vi) ≠ (vj, uj) are satisfied for all 1 ≤ i < j ≤ M.
.Output: Print an integer that denotes the number of triples that satisfy the mentioned condition.
Explanation: The triplets are: {(1, 2, 3), (1, 2, 4), (2, 3, 4), (1, 3, 4)}
152 | P a g e
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in
red and has cost 100 + 600 = 700.
Note that the path through cities [0, 1, 2, 3] is cheaper but is invalid because it uses 2 stops.
Input: n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The graph is shown above. The optimal path with at most 1 stop from city 0 to 2 is marked
in red and has cost 100 + 100 = 200.
153 | P a g e
Input: graph = [[1, 2], [3], [3], []]
Output: [[0, 1, 3], [0, 2, 3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
154 | P a g e
21.10 All Ancestors of a Node in a Directed Acyclic Graph
You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The
nodes are numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges, where edges[i]
= [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph. Return a list answer,
where answer[i] is the list of ancestors of the ith node, sorted in ascending order. A node u is an ancestor of
another node v if u can reach v via a set of edges.
Input: n = 8, edgeList = [[0, 3], [0, 4], [1, 3], [2, 4], [2, 7], [3, 5], [3, 6], [3, 7], [4, 6]]
Output: [[], [], [], [0, 1], [0, 2], [0, 1, 3], [0, 1, 2, 3, 4], [0, 1, 2, 3]]
Explanation:
The above diagram represents the input graph.
- Nodes 0, 1, and 2 do not have any ancestors.
- Node 3 has two ancestors 0 and 1.
- Node 4 has two ancestors 0 and 2.
- Node 5 has three ancestors 0, 1, and 3.
- Node 6 has five ancestors 0, 1, 2, 3, and 4.
- Node 7 has four ancestors 0, 1, 2, and 3.
Input: n = 5, edgeList = [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Output: [[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]]
155 | P a g e
Explanation:
The above diagram represents the input graph.
- Node 0 does not have any ancestor.
- Node 1 has one ancestor 0.
- Node 2 has two ancestors 0 and 1.
- Node 3 has three ancestors 0, 1, and 2.
- Node 4 has four ancestors 0, 1, 2, and 3.
21.11 Reorder Routes to Make All Paths Lead to the City Zero
There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between
two different cities (this network form a tree). Last year, the ministry of transport decided to orient the roads
in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0. Return
the minimum number of edges changed.
It's guaranteed that each city can reach city 0 after reorder.
Input: n = 6, connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Input: n = 5, connections = [[1, 0], [1, 2], [3, 2], [3, 4]]
Output: 2
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Input: n = 3, connections = [[1, 0], [2, 0]]
Output: 0
156 | P a g e
• If isWater[i][j] == 0, cell (i, j) is a land cell.
• If isWater[i][j] == 1, cell (i, j) is a water cell.
You must assign each cell a height in a way that follows these rules:
• The height of each cell must be non-negative.
• If the cell is a water cell, its height must be 0.
• Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to
another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are
touching).
Find an assignment of heights such that the maximum height in the matrix is maximized.
Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple
solutions, return any of them.
157 | P a g e
You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's
(representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells
outside of the grid are considered water cells.
An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that
make up this island in grid2.
Return the number of islands in grid2 that are considered sub-islands.
Input: grid1= [[1, 1, 1, 0, 0], [0, 1, 1, 1, 1], [0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 1, 0, 1, 1]],
grid2 = [[1, 1, 1, 0, 0], [0, 0, 1, 1, 1], [0, 1, 0, 0, 0], [1, 0, 1, 1, 0], [0, 1, 0, 1, 0]]
Output: 3
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.
Input: grid1 = [[1, 0, 1, 0, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 0, 1, 0, 1]],
grid2 = [[0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [1, 0, 0, 0, 1]]
Output: 2
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.
158 | P a g e
2. Everybody (except for the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.
You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person
labeled bi. If a trust relationship does not exist in trust array, then such a trust relationship does not exist.
Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
Input: n = 2, trust = [[1, 2]]
Output: 2
Input: n = 3, trust = [[1, 3], [2, 3]]
Output: 3
Input: n = 3, trust = [[1, 3], [2, 3], [3, 1]]
Output: -1
Output: 2
Input: isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
Output: 3
159 | P a g e
There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by
a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning
there is an edge from node i to each node in graph[i].
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path
starting from that node leads to a terminal node (or another safe node).
Return an array containing all the safe nodes of the graph. The answer should be sorted
in ascending order.
Input: graph = [[1, 2], [2, 3], [5], [0], [5], [], []]
Output: [2, 4, 5, 6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.
Input: graph = [[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.
Return true if you can finish all courses. Otherwise, return false.
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished
course 1. So it is impossible.
160 | P a g e
21.18 Redundant Connection
In this problem, a tree is an undirected graph that is connected and has no cycles.
You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge
added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already
existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there
is an edge between nodes ai and bi in the graph.
Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple
answers, return the answer that occurs last in the input.
Input: edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
Output: [1, 4]
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive
the signal. If it is impossible for all the n nodes to receive the signal, return -1.
161 | P a g e
Input: times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2
Output: 2
Input: times = [[1, 2, 1]], n = 2, k = 1
Output: 1
Input: times = [[1, 2, 1]], n = 2, k = 2
Output: -1
162 | P a g e
Input: graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge
connects a node in one and a node in the other.
Input: graph = [[1, 3], [0, 2], [1, 3], [0, 2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting
which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if
you can visit all the rooms, or false otherwise.
Input: rooms = [[1], [2], [3], []]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.
Input: rooms = [[1, 3], [3, 0, 1], [2], [0]]
Output: false
Explanation: We cannot enter room number 2 since the only key that unlocks it is in that room.
There are n nodes and m bridges in between these nodes. Print the possible path through each node using
each edges (if possible), traveling through each edges only once.
Input: A 2D array graph [V][V] where V is the number of vertices in graph and graph [V][V] is adjacency
matrix representation of the graph. A value graph[i][j] is 1 if there is a direct edge from i to j, otherwise
graph[i][j] is 0.
Output: An array path [V] that should contain the Hamiltonian Path. Path [i] should represent the ith vertex
in the Hamiltonian Path. The code should also return false if there is no Hamiltonian Cycle in the graph.
164 | P a g e
(0)--(1)--(2)
| /\ |
| / \ |
| / \ |
(3)-------(4)
(0)--(1)--(2)
| /\ |
| / \ |
| / \ |
(3) (4)
Backtracking Algorithm: Create an empty path array and add vertex 0 to it. Add other vertices, starting
from the vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex
and not already added. If we find such a vertex, we add the vertex as part of the solution. If we do not find
a vertex then we return false.
Complete Graph: A graph is said to be complete if each possible vertices is connected through an Edge.
Hamiltonian Cycle: It is a closed walk such that each vertex is visited at most once except the initial vertex.
and it is not necessary to visit all the edges.
Formula: (N – 1)! / 2
Input: N = 6
Output: Hamiltonian cycles = 60
Input: N = 4
Output: Hamiltonian cycles = 3
Explanation: Let us take the example of N = 4 complete undirected graph, The 3 different Hamiltonian
cycle is as shown below:
165 | P a g e
22. Graph Traversal
22.1 Minimum Time to Collect All Apples in a Tree
Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their
vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you
have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.
The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an
edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] =
true means that vertex i has an apple; otherwise, it does not have any apple.
Input: n = 7, edges = [[0, 1], [0, 2], [1, 4], [1, 5], [2, 3], [2, 6]], hasApple = [false, false, true, false, true, true,
false]
Output: 8
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal
path to collect all apples is shown by the green arrows.
Input: n = 7, edges = [[0, 1], [0, 2], [1, 4], [1, 5], [2, 3], [2, 6]], hasApple = [false, false, true, false, false, true,
false]
Output: 6
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal
path to collect all apples is shown by the green arrows.
Input: n = 7, edges = [[0, 1], [0, 2], [1, 4], [1, 5], [2, 3], [2, 6]], hasApple = [false, false, false, false, false, false,
false]
Output: 0
166 | P a g e
22.2 Depth First Search
Depth First Traversal (or DFS) for a graph is similar to Depth First Traversal of a tree. The only catch here
is, that, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node
more than once, use a boolean visited array. A graph can have more than one DFS traversal.
For a given graph G, print DFS traversal from a given source vertex.
Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Explanation:
DFS Diagram:
Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Explanation:
DFS Diagram:
167 | P a g e
Return the number of minutes needed for the entire tree to be infected.
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible
route that visits every city exactly once and returns to the starting point. The problem statement gives a list
of cities along with the distances between each city.
Objective: To start from the origin city, visit other cities only once, and return to the original city again. Our
target is to find the shortest possible path to complete the round-trip route.
168 | P a g e
Here a graph is given where 1, 2, 3, and 4 represent the cities, and the weight associated with every edge
represents the distance between those cities. The goal is to find the shortest possible path for the tour that
starts from the origin city, traverses the graph while only visiting the other cities or nodes once, and returns
to the origin city.
For the above graph, the optimal route is to follow the minimum cost path: 1 – 2 – 4 – 3 - 1. And this
shortest route would cost 10 + 25 + 30 + 15 =80
Algorithm for Traveling Salesman Problem: We will use the dynamic programming approach to solve
the Travelling Salesman Problem (TSP).
Let’s assume S is the subset of cities and belongs to {1, 2, 3, …, n} where 1, 2, 3…n are the cities and i, j are
two cities in that subset. Now cost(i, S, j) is defined in such a way as the length of the shortest path visiting
node in S, which is exactly once having the starting and ending point as i and j respectively.
For example, cost (1, {2, 3, 4}, 1) denotes the length of the shortest path where:
• Starting city is 1
• Cities 2, 3, and 4 are visited only once
• The ending point is 1
For the given figure above, the adjacency matrix would be the following:
dist(i, j) 1 2 3 4
1 0 10 15 20
169 | P a g e
2 10 0 35 25
3 15 35 0 30
4 20 25 30 0
Now S = {1, 2, 3, 4}. There are four elements. Hence the number of subsets will be 2^4 or 16. Those
subsets are-
1) |S| = Null:
{Φ}
2) |S| = 1:
{{1}, {2}, {3}, {4}}
3) |S| = 2:
{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
4) |S| = 3:
{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}
5) |S| = 4:
{{1, 2, 3, 4}}
As we are starting at 1, we could discard the subsets containing city 1. The algorithm calculation steps:
1) |S| = Φ:
cost (2, Φ, 1) = dist(2, 1) = 10
cost (3, Φ, 1) = dist(3, 1) = 15
cost (4, Φ, 1) = dist(4, 1) = 20
2) |S| = 1:
cost (2, {3}, 1) = dist(2, 3) + cost (3, Φ, 1) = 35+15 = 50
cost (2, {4}, 1) = dist(2, 4) + cost (4, Φ, 1) = 25+20 = 45
cost (3, {2}, 1) = dist(3, 2) + cost (2, Φ, 1) = 35+10 = 45
cost (3, {4}, 1) = dist(3, 4) + cost (4, Φ, 1) = 30+20 = 50
cost (4, {2}, 1) = dist(4, 2) + cost (2, Φ, 1) = 25+10 = 35
cost (4, {3}, 1) = dist(4, 3) + cost (3, Φ, 1) = 30+15 = 45
3) |S| = 2:
cost (2, {3, 4}, 1) = min [ dist[2,3] + Cost(3,{4},1) = 35+50 = 85,
dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70
cost (3, {2, 4}, 1) = min [ dist[3,2] + Cost(2,{4},1) = 35+45 = 80,
dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65
cost (4, {2, 3}, 1) = min [ dist[4,2] + Cost(2,{3},1) = 25+50 = 75
dist[4,3] + Cost(3,{2},1) = 30+45 = 75 ] = 75
4) |S| = 3:
cost (1, {2, 3, 4}, 1) = min [ dist[1,2]+Cost(2,{3,4},1) = 10+70 = 80
dist[1,3]+Cost(3,{2,4},1) = 15+65 = 80
dist[1,4]+Cost(4,{2,3},1) = 20+75 = 95 ] = 80
170 | P a g e
23.2 Shortest Paths from Source to all Vertices (Dijkstra's Algorithm)
Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the
given graph.
Output: 0 4 12 19 21 11 9 8 14
171 | P a g e
Output: 4
Cycle 6 -> 1 -> 5 -> 0 -> 6
Output: 3
Cycle 6 -> 1 -> 2 -> 6
Input: M = 2, N = 2
Output: 2
Input: M = 2, N = 3
Output: 3
Count all possible paths: We can recursively move to right and down from the start until we reach the
destination and then add up all valid paths to get the answer.
Procedure:
• Create a recursive function with parameters as row and column index
• Call this recursive function for N-1 and M-1
• In the recursive function
• If N == 1 or M == 1 then return 1
• else call the recursive function with (N-1, M) and (N, M-1) and return the sum of this
• Print the answer
172 | P a g e
23.5 Number of Ways to Arrive at Destination
You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between
some intersections. The inputs are generated such that you can reach any intersection from any other
intersection and that there is at most one road between any two intersections.
You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a
road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways
you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.
Return the number of ways you can arrive at your destination in the shortest amount of time. Since the
answer may be large, return it modulo 109 + 7.
The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|.
173 | P a g e
There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1i, y1i,
x2i, y2i, costi] indicates that the ith special road can take you from (x1i, y1i) to (x2i, y2i) with a cost equal
to costi. You can use each special road any number of times.
Return the minimum cost required to go from (startX, startY) to (targetX, targetY).
Output: 5
- (1,2) -> (3,3). This move uses the first special edge, the cost is 2.
- (3,4) -> (4,5). This move uses the second special edge, the cost is 1.
Output: 7
Explanation: It is optimal to not use any special edges and go directly from the starting to the ending
position with a cost |5 - 3| + |7 - 2| = 7.
Return the length of the shortest path that visits every node. You may start and stop at any node, you may
revisit nodes multiple times, and you may reuse edges.
174 | P a g e
Explanation: One possible path is [1, 0, 2, 0, 3]
Input: graph = [[1], [0, 2, 4], [1, 3, 4], [2], [1, 2]]
Output: 4
Explanation: One possible path is [0, 1, 4, 2, 3]
175 | P a g e
Basic Greedy Coloring Algorithm:
1. Color first vertex with first color.
2. Do following for remaining V-1 vertices.
a) Consider the currently picked vertex and color it with the lowest numbered color that has not been
used on any previously colored vertices adjacent to it. If all previously used colors appear on vertices
adjacent to v, assign a new color to it.
Output:
Coloring of graph 1
Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 2
Vertex 3 ---> Color 0
Vertex 4 ---> Color 1
Coloring of graph 2
Vertex 0 ---> Color 0
Vertex 1 ---> Color 1
Vertex 2 ---> Color 2
Vertex 3 ---> Color 0
Vertex 4 ---> Color 3
Approach:
• If the no. of vertices is Even then it is Even Cycle and to color such graph we require 2 colors.
• If the no. of vertices is Odd then it is Odd Cycle and to color such graph we require 3 colors.
Input: Vertices = 3
Output: No. of colors require is: 3
Input: vertices = 4
Output: No. of colors require is: 2
Color required = 2
176 | P a g e
Example 2: Odd Cycle: Number of vertices = 5
Color required = 3
Note: Here coloring of a graph means the assignment of colors to all vertices. Following is an example of a
graph that can be colored with 3 different colors:
177 | P a g e
{1, 1, 0, 1},
{1, 0, 1, 0}
Output: Solution Exists: Following are the assigned colors: 1 2 3 2
Explanation: By coloring the vertices with following colors, adjacent vertices does not have same colors
Input: u1 = 1, v1 = 4
u2 = 1, v2 = 2
u3 = 2, v3 = 3
u4 = 3, v4 = 4
The above input shows the pair of vertices (ui, vi) who have an edge between them. The output shows the
color assigned to the respective edges.
Edge colorings are one of several different types of graph coloring problems. The above figure of a Graph
shows an edge coloring of a graph by the colors green and black, in which no adjacent edge have the
same color.
178 | P a g e
Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot
see the answers of the student sitting directly in front or behind him. Return the maximum number of
students that can take the exam together without any cheating being possible.
Students must be placed in seats in good condition.
179 | P a g e
Return the XOR sum after the rearrangement.
180 | P a g e
25.4 Maximum AND Sum of Array
You are given an integer array nums of length n and an integer numSlots such that 2 * numSlots >= n.
There are numSlots slots numbered from 1 to numSlots.
You have to place all n integers into the slots such that each slot contains at most two numbers. The AND
sum of a given placement is the sum of the bitwise AND of every number with its respective slot number.
• For example, the AND sum of placing the numbers [1, 3] into slot 1 and [4, 6] into slot 2 is equal to (1
AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4.
Return the maximum possible AND sum of nums given numSlots slots.
26. Trees
26.1 Maximum Difference between Node and Ancestor
Given the root of a binary tree, find the maximum value v for which there
exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.
A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.
181 | P a g e
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
183 | P a g e
Input: root = [1, null, 2, 3]
Output: [1, 3, 2]
Input: root = []
Output: []
Input: root = [1]
Output: [1]
184 | P a g e
Input: root = [1, null, 2]
Output: 2
.
Input: root = [3, 9, 20, null, null, 15, 7]
Output: true
185 | P a g e
Input: root = [3, 9, 20, null, null, 15, 7]
Output: 2
Input: root = [2, null, 3, null, 4, null, 5, null, 6]
Output: 5
186 | P a g e
A leaf node is a node with no children.
187 | P a g e
3. Repeat step#2 until there are (V-1) edges in the spanning tree.
Kruskal’s algorithm to find the minimum cost spanning tree uses the greedy approach. The Greedy Choice
is to pick the smallest weight edge that does not cause a cycle in the MST constructed so far.
Input: For the given graph G find the minimum cost spanning tree.
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having (9 – 1)
= 8 edges.
After sorting:
Now pick all edges one by one from the sorted list of edges.
Output:
0 -- 3 == 5
0 -- 1 == 10
Prim’s Algorithm:
The working of Prim’s algorithm can be described by using the following steps:
1. Determine an arbitrary vertex as the starting vertex of the MST.
2. Follow steps 3 to 5 till there are vertices that are not included in the MST (known as fringe vertex).
3. Find edges connecting any tree vertex with the fringe vertices.
4. Find the minimum among these edges.
5. Add the chosen edge to the MST if it does not form any cycle.
6. Return the MST and exit
Input: For the given graph G find the minimum cost spanning tree.
Output: The final structure of the MST is as follows and the weight of the edges of the MST is (4 + 8 + 1 +
2 + 4 + 2 + 7 + 9) = 37.
Output:
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5
189 | P a g e
27.3 Total Number of Spanning Trees in a Graph
If a graph is a complete graph with n vertices, then total number of spanning trees is n (n-2) where n is the
number of nodes in the graph. In complete graph, the task is equal to counting different labeled trees with
n nodes for which have Cayley’s formula.
Laplacian matrix:
A Laplacian matrix L, where L[i, i] is the degree of node i and L[i, j] = −1 if there is an edge between nodes i
and j, and otherwise L[i, j] = 0.
Kirchhoff’s theorem provides a way to calculate the number of spanning trees for a given graph as a
determinant of a special matrix. Consider the following graph,
In order to calculate the number of spanning trees, construct a Laplacian matrix L, where L[i, i] is the degree
of node i and L[i, j] = −1 if there is an edge between nodes i and j, and otherwise L[i, j] = 0.
for the above graph, The Laplacian matrix will look like this
The Determinant of a matrix that can be obtained when we remove any row and any column from L.
For example, if we remove the first row and column, the result will be,
The determinant is always the same, regardless of which row and column we remove from L.
190 | P a g e
27.4 Minimum Product Spanning Tree
A minimum product spanning tree for a weighted, connected, and undirected graph is a spanning tree with
a weight product less than or equal to the weight product of every other spanning tree. The weight product
of a spanning tree is the product of weights corresponding to each edge of the spanning tree. All weights
of the given graph will be positive for simplicity.
Input:
Output: Minimum Product that we can obtain is 180 for above graph by choosing edges 0-1, 1-2, 0-3 and
1-4
This problem can be solved using standard minimum spanning tree algorithms like Kruskal and prim’s
algorithm, but we need to modify our graph to use these algorithms. Minimum spanning tree algorithms
tries to minimize the total sum of weights, here we need to minimize the total product of weights. We can
use the property of logarithms to overcome this problem.
log(w1* w2 * w3 * …. * wN) = log(w1) + log(w2) + log(w3) ….. + log(wN)
We can replace each weight of the graph by its log value, then we apply any minimum spanning tree
algorithm which will try to minimize the sum of log(wi) which in turn minimizes the weight product.
Algorithm:
1. Sort all edges of graph in non-increasing order of edge weights.
2. Initialize MST as original graph and remove extra edges using step 3.
3. Pick highest weight edge from remaining edges and check if deleting the edge disconnects the
graph or not.
If disconnects, then we don’t delete the edge.
Else we delete the edge and continue.
191 | P a g e
If we delete highest weight edge of weight 14, graph doesn’t become disconnected, so we remove it.
192 | P a g e
We continue this way and following edges remain in final MST.
Edges in MST
(3, 4)
(0, 7)
(2, 3)
(2, 5)
(0, 1)
(5, 6)
(2, 8)
(6, 7)
Output: Yes
Explanation: The diagram clearly shows a cycle 0 -> 2 -> 0
Input: people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
Output: [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]] is the reconstructed queue.
Input: people = [[6, 0], [5, 0], [4, 0], [3, 2], [2, 2], [1, 4]]
Output: [[4, 0], [5, 0], [2, 2], [3, 2], [1, 4], [6, 0]]
193 | P a g e
28.2 Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest increasing subsequences.
Notice that the sequence has to be strictly increasing.
Input
["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"]
[[4], [3], [], [1], [], [2], []]
Output
[null, null, 0, null, 1, null, 3]
Explanation
LUPrefix server = new LUPrefix(4); // Initialize a stream of 4 videos.
server.upload(3); // Upload video 3.
server.longest(); // Since video 1 has not been uploaded yet, there is no prefix.
// So, we return 0.
server.upload(1); // Upload video 1.
server.longest(); // The prefix [1] is the longest uploaded prefix, so we return 1.
server.upload(2); // Upload video 2.
server.longest(); // The prefix [1,2,3] is the longest uploaded prefix, so we return 3.
194 | P a g e
28.4 Falling Squares
There are several squares being dropped onto the X-axis of a 2D plane.
You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square
with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.
Each square is dropped one at a time from a height above any landed squares. It then falls downward
(negative Y direction) until it either lands on the top side of another square or on the X-axis. A square
brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in
place and cannot be moved.
After each square is dropped, you must record the height of the current tallest stack of squares.
Return an integer array ans where ans[i] represents the height described above after dropping
the ith square.
28.5 My Calendar I
You are implementing a program to use as your calendar. We can add a new event if adding the event will
not cause a double booking.
A double booking happens when two events have some non-empty intersection (i.e., some moment is
common to both events.).
The event can be represented as a pair of integers start and end that represents a booking on the half-open
interval [start, end), the range of real numbers x such that start <= x < end.
Implement the MyCalendar class:
• MyCalendar() Initializes the calendar object.
• boolean book(int start, int end) Returns true if the event can be added to the calendar successfully
without causing a double booking. Otherwise, return false and do not add the event to the
calendar.
• The base case of this problem is if the number of vertices with an odd number of edges(i.e. odd
degree) is greater than 2 then there is no Eulerian path.
• If it has the solution and all the nodes have an even number of edges then we can start our path from
any of the nodes.
• If it has the solution and exactly two vertices have an odd number of edges then we have to start our
path from one of these two vertices.
• There will not be the case where exactly one vertex has an odd number of edges, as there is an even
number of edges in total.
197 | P a g e
29.2 Reconstruct Itinerary
You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival
airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If
there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when
read as a single string.
• For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only
once.
Input: tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
Output: ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]
Explanation: Another possible reconstruction is ["JFK", "SFO", "ATL", "JFK", "ATL", "SFO"] but it is larger in
lexical order.
Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.
Input: n = 2, k = 2
Output: "01100"
Explanation: For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.
199 | P a g e
Output: [[1, 2], [2, 1], [1, 3]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2
200 | P a g e
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.
Input: servers = [5, 1, 4, 3, 2], tasks = [2, 1, 2, 4, 5, 2, 1]
Output: [1, 4, 1, 4, 1, 3, 2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4.
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9.
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.
201 | P a g e
[[], [1], [2], [], [3], []]
Output: [null, null, null, 1.5, null, 2.0]
Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
Input: n = 5, edges = [[0, 1, 1], [1, 2, 1], [2, 3, 2], [0, 3, 2], [0, 4, 3], [3, 4, 3], [1, 4, 6]]
Output: [[0, 1], [2, 3, 4, 5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:
202 | P a g e
Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them
in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges.
We add them to the second list of the output.
Input: n = 4, edges = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 1]]
Output: [[], [0, 1, 2, 3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the
given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
203 | P a g e
In one day, we are allowed to change any single land cell (1) into a water cell (0).
Return the minimum number of days to disconnect the grid.
204 | P a g e
Input: n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
Output: [0, 0, 1, 3]
Explanation: In the first query, all the edges in the path from 0 to 3 have a weight of 1. Hence, the answer
is 0.
In the second query, all the edges in the path from 3 to 6 have a weight of 2. Hence, the answer is 0.
In the third query, we change the weight of edge [2, 3] to 2. After this operation, all the edges in the path
from 2 to 6 have a weight of 2. Hence, the answer is 1.
In the fourth query, we change the weights of edges [0, 1], [1, 2] and [2, 3] to 2. After these operations, all
the edges in the path from 0 to 6 have a weight of 2. Hence, the answer is 3.
For each queries[i], it can be shown that answer[i] is the minimum number of operations needed to equalize
all the edge weights in the path from ai to bi.
Input: n = 8, edges = [[1, 2, 6], [1, 3, 4], [2, 4, 6], [2, 5, 3], [3, 6, 6], [3, 0, 8], [7, 0, 2]], queries = [[4, 6], [0, 4],
[6, 5], [7, 4]]
Output: [1, 2, 2, 3]
Explanation: In the first query, we change the weight of edge [1, 3] to 6. After this operation, all the edges
in the path from 4 to 6 have a weight of 6. Hence, the answer is 1.
In the second query, we change the weight of edges [0, 3] and [3, 1] to 6. After these operations, all the
edges in the path from 0 to 4 have a weight of 6. Hence, the answer is 2.
In the third query, we change the weight of edges [1, 3] and [5, 2] to 6. After these operations, all the edges
in the path from 6 to 5 have a weight of 6. Hence, the answer is 2.
In the fourth query, we change the weights of edges [0, 7], [0, 3] and [1, 3] to 6. After these operations, all
the edges in the path from 7 to 4 have a weight of 6. Hence, the answer is 3.
205 | P a g e
For each queries[i], it can be shown that answer[i] is the minimum number of operations needed to equalize
all the edge weights in the path from ai to bi.
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Input: n = 0
Output: 0
Input: n = 1
Output: 0
Input: p = 2, q = 1
Output: 2
Explanation: The ray meets receptor 2 the first time it gets reflected back to the left wall.
Input: p = 3, q = 1
Output: 1
Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.
Input: n = 3
Output: ["1/2","1/3","2/3"]
Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".
207 | P a g e
32.5 The kth Factor of n
You are given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i
== 0.
Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -
1 if n has less than k factors.
Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.
Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.
Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.
Example 1:
208 | P a g e
Input: nums = [6, 10, 3]
Output: 5
Explanation: The figure shows all the non-empty subsequences and their GCDs.
The different GCDs are 6, 10, 3, 2, and 1.
Input: nums = [5, 15, 40, 5, 6]
Output: 7
209 | P a g e
Input: rectangles = [[4, 8], [3, 6], [10, 20], [15, 30]]
Output: 6
Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):
- Rectangle 0 with rectangle 1: 4/8 == 3/6.
- Rectangle 0 with rectangle 2: 4/8 == 10/20.
- Rectangle 0 with rectangle 3: 4/8 == 15/30.
- Rectangle 1 with rectangle 2: 3/6 == 10/20.
- Rectangle 1 with rectangle 3: 3/6 == 15/30.
- Rectangle 2 with rectangle 3: 10/20 == 15/30.
Input: rectangles = [[4, 5], [7, 8]]
Output: 0
Explanation: There are no interchangeable pairs of rectangles.
210 | P a g e
Explanation:
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2, 2, 1, 1, 3, 3].
- (3, 3) are non-coprime with LCM(3, 3) = 3. Now, nums = [2, 2, 1, 1, 3].
- (2, 2) are non-coprime with LCM(2, 2) = 2. Now, nums = [2, 1, 1, 3].
There are no more adjacent non-coprime numbers in nums.
Thus, the final modified array is [2, 1, 1, 3].
Note that there are other ways to obtain the same resultant array.
33. Combinatorics
33.1 Vowels of All Substrings
Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring
of word.
A substring is a contiguous (non-empty) sequence of characters within a string.
Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful
during the calculations.
211 | P a g e
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.
Input: word = "abc"
Output: 3
Explanation:
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.
Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".
212 | P a g e
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.
Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.
Input: n = 5, limit = 2
Output: 3
Explanation: There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2),
(2, 1, 2) and (2, 2, 1).
Input: n = 3, limit = 3
Output: 10
213 | P a g e
Explanation: There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0,
3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).
Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].
Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].
Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].
Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.
Input: n = 2
Output: 6
Explanation: All possible orders:
(P1, P2, D1, D2), (P1, P2, D2, D1), (P1, D1, P2, D2), (P2, P1, D1, D2), (P2, P1, D2, D1) and (P2, D2, P1, D1).
This is an invalid order (P1, D2, P2, D1) because Pickup 2 is after of Delivery 2.
Input: n = 3
Output: 90
215 | P a g e
Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].
Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.
Input: n = 33
Output: 66045
216 | P a g e
Input: s = "cba"
Output: 5
Explanation: The simulation goes as follows:
Operation 1: i=2, j=2. Swap s[1] and s[2] to get s="cab", then reverse the suffix starting at 2. Now, s="cab".
Operation 2: i=1, j=2. Swap s[0] and s[2] to get s="bac", then reverse the suffix starting at 1. Now, s="bca".
Operation 3: i=2, j=2. Swap s[1] and s[2] to get s="bac", then reverse the suffix starting at 2. Now, s="bac".
Operation 4: i=1, j=1. Swap s[0] and s[1] to get s="abc", then reverse the suffix starting at 1. Now, s="acb".
Operation 5: i=2, j=2. Swap s[1] and s[2] to get s="abc", then reverse the suffix starting at 2. Now, s="abc".
Input: s = "aabaa"
Output: 2
Explanation: The simulation goes as follows:
Operation 1: i=3, j=4. Swap s[2] and s[4] to get s="aaaab", then reverse the substring starting at 3. Now,
s="aaaba".
Operation 2: i=4, j=4. Swap s[3] and s[4] to get s="aaaab", then reverse the substring starting at 4. Now,
s="aaaab".
34. Probability
34.1 Soup Servings
There are two types of soup: type A and type B. Initially, we have n ml of each type of soup. There are four
kinds of operations:
1. Serve 100 ml of soup A and 0 ml of soup B,
2. Serve 75 ml of soup A and 25 ml of soup B,
3. Serve 50 ml of soup A and 50 ml of soup B, and
4. Serve 25 ml of soup A and 75 ml of soup B.
When we serve some soup, we give it to someone, and we no longer have it. Each turn, we will choose from
the four operations with an equal probability 0.25. If the remaining volume of soup is not enough to
complete the operation, we will serve as much as possible. We stop once we no longer have some quantity
of both types of soup.
Note that we do not have an operation where all 100 ml's of soup B are used first.
Return the probability that soup A will be empty first, plus half the probability that A and B become empty
at the same time. Answers within 10-5 of the actual answer will be accepted.
Input: n = 50
Output: 0.62500
Explanation: If we choose the first two operations, A will become empty first.
For the third operation, A and B will become empty at the same time.
For the fourth operation, B will become empty first.
So the total probability of A becoming empty first plus half the probability that A and B become empty at
the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.
217 | P a g e
Input: n = 100
Output: 0.71875
218 | P a g e
Input: count =
[0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000, 3.00000, 2.37500, 2.50000, 3.00000]
Explanation: The sample represented by count is [1, 2, 2, 2, 3, 3, 3, 3].
The minimum and maximum are 1 and 3 respectively.
The mean is (1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375.
Since the size of the sample is even, the median is the average of the two middle elements 2 and 3, which
is 2.5.
The mode is 3 as it appears the most in the sample.
Input: count =
[0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000, 4.00000, 2.18182, 2.00000, 1.00000]
Explanation: The sample represented by count is [1,1,1,1,2,2,2,3,3,4,4].
The minimum and maximum are 1 and 4 respectively.
The mean is (1+1+1+1+2+2+2+3+3+4+4) / 11 = 24 / 11 = 2.18181818... (for display purposes, the
output shows the rounded number 2.18182).
Since the size of the sample is odd, the median is the middle element 2.
The mode is 1 as it appears the most in the sample.
Input: n = 1
Output: 1.00000
Explanation: The first person can only get the first seat.
Input: n = 2
Output: 0.50000
Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the
first seat).
219 | P a g e
34.5 Implement Rand10() Using Rand7()
Given the API rand7() that generates a uniform random integer in the range [1, 7], write a
function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the
API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API.
Each test case will have one internal argument n, the number of times that your implemented
function rand10() will be called while testing. Note that this is not an argument passed to rand10().
Input: n = 1
Output: [2]
Input: n = 2
Output: [2, 8]
Input: n = 3
Output: [3, 8, 10]
Input: n = 3, edges = [[0, 1], [1, 2], [0, 2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other
has 0.5 * 0.5 = 0.25.
220 | P a g e
Input: n = 3, edges = [[0, 1], [1, 2], [0, 2]], succProb = [0.5, 0.5, 0.3], start = 0, end = 2
Output: 0.30000
34.7 Probability of a Two Boxes having the Same Number of Distinct Balls
Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the
number of balls of color i.
All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box
and the remaining n balls to the other box (Please read the explanation of the second example carefully).
Please note that the two boxes are considered different. For example, if we have two balls of colors a and b,
and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a)
(Please read the explanation of the first example carefully).
Return the probability that the two boxes have the same number of distinct balls. Answers within 10-5 of the
actual value will be accepted as correct.
35. Cycle-Finding
35.1 Detect Cycles in 2D Grid
Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of
the same value in grid.
A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell,
you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it
has the same value of the current cell.
Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -
> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.
Return true if any cycle of the same value exists in grid, otherwise, return false.
Input: grid = [["a", "a", "a", "a"], ["a", "b", "b", "a"], ["a", "b", "b", "a"], ["a", "a", "a", "a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:
Input: grid = [["c", "c", "c", "a"], ["c", "d", "c", "c"], ["c", "c", "e", "c"], ["f", "c", "c", "c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:
Input: grid = [["a", "b", "b"], ["b", "z", "b"], ["b", "b", "a"]]
Output: false
Input: n = 7, edges = [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 6], [6, 3]]
Output: 3
Explanation: The cycle with the smallest length is : 0 -> 1 -> 2 -> 0
223 | P a g e
36. Matrices
36.1 Valid Sudoku
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the
following rules:
1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
224 | P a g e
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there
are two 8's in the top left 3x3 sub-box, it is invalid.
Input: matrix = [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]]
Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]
225 | P a g e
Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Input: matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
Output: true
Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13
Output: false
Input: matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], target
=5
Output: true
227 | P a g e
Input: matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]], target
= 20
Output: false
Input: grid = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.
Input: grid = [[1]]
Output: 4
Input: grid = [[1, 0]]
Output: 4
36.8 01 Matrix
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
228 | P a g e
Input: mat = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
229 | P a g e
Input: mat = [[1, 2], [3, 4]], r = 2, c = 4
Output: [[1, 2], [3, 4]]
230 | P a g e
Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.
Input: n = 1
Output: true
Example 3:
Input: n = 2
Output: true
232 | P a g e
37.5 Cat and Mouse
A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.
The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.
The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at
node 0.
During each player's turn, they must travel along one edge of the graph that meets where they are. For
example, if the Mouse is at node 1, it must travel to any node in graph[1].
Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)
Then, the game can end in three ways:
• If ever the Cat occupies the same node as the Mouse, the Cat wins.
• If ever the Mouse reaches the Hole, the Mouse wins.
• If ever a position is repeated (i.e., the players are in the same position as a previous turn, and it is the
same player's turn to move), the game is a draw.
Given a graph, and assuming both players play optimally, return
• 1 if the mouse wins the game,
• 2 if the cat wins the game, or
• 0 if the game is a draw.
Input: graph = [[2, 5], [3], [0, 4, 5], [1, 4, 5], [2, 3], [0, 2, 3]]
Output: 0
233 | P a g e
Input: graph = [[1, 3], [0], [3], [0, 2]]
Output: 1
Input: n = 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.
Input: n = 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.
234 | P a g e
Input: piles = [2, 4, 5]
Output: 4
Input: piles = [9, 8, 7, 6, 5, 1, 2, 3, 4]
Output: 18
235 | P a g e
Alice and Bob take turns, with Alice starting first. Initially, M = 1.
On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <=
2M. Then, we set M = max(M, X).
The game continues until all the stones have been taken.
Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.
Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
- The range is [1, 10]. Guess 7.
236 | P a g e
- If this is my number, your total is $0. Otherwise, you pay $7.
- If my number is higher, the range is [8, 10]. Guess 9.
- If this is my number, your total is $7. Otherwise, you pay $9.
- If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
- If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
- If my number is lower, the range is [1, 6]. Guess 3.
- If this is my number, your total is $7. Otherwise, you pay $3.
- If my number is higher, the range is [4,6]. Guess 5.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
- If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
- If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
- If my number is lower, the range is [1,2]. Guess 1.
- If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.
Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.
Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
- Guess 1.
- If this is my number, your total is $0. Otherwise, you pay $1.
- If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.
38. Geometry
38.1 Rectangle Area
Given the coordinates of two rectilinear rectangles in a 2D plane, return the total area covered by the two
rectangles.
The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).
The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).
237 | P a g e
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16
238 | P a g e
Input: points = [[0, 0], [0, 1], [1, 0], [0, 2], [2, 0]]
Output: 2.00000
Explanation: The five points are shown in the above figure. The red triangle is the largest.
Input: points = [[1, 0], [0, 0], [0, 1]]
Output: 0.50000
239 | P a g e
Input: grid = [[1, 2], [3, 4]]
Output: 34
240 | P a g e
Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false
242 | P a g e
Given the integer n, return the minimum number of cuts needed to divide a circle into n equal slices.
Input: n = 4
Output: 2
Explanation:
The above figure shows how cutting the circle twice through the middle divides it into 4 equal slices.
Input: n = 3
Output: 3
Explanation:
At least 3 cuts are needed to divide the circle into 3 equal slices.
It can be shown that less than 3 cuts cannot result in 3 slices of equal size and shape.
Also note that the first cut will not divide the circle into distinct parts.
243 | P a g e
You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie
in its range. These bombs will further detonate the bombs that lie in their ranges.
Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed
to detonate only one bomb.
244 | P a g e
Input: bombs = [[1, 2, 3], [2, 3, 1], [3, 4, 2], [4, 5, 3], [5, 6, 4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.
It is easy to solve the problem in O(n2) time, because we can go through all possible pairs of line segments
and check if they intersect. But we can solve this problem more efficiently in O(n log n) time using a sweep
line algorithm and a range query data structure.
The idea is to process the endpoints of the line segments from left to right and focus on three types of
events:
1. Horizontal segment begins
2. Horizontal segment ends
3. Vertical segment
245 | P a g e
The following events correspond to the example:
We go through the events from left to right and use a data structure that maintains a set of y coordinates
where there is an active horizontal segment. At event 1, we add the y coordinate of the segment to the set,
and at event 2, we remove the y coordinate from the set.
Intersection points are calculated at event 3. When there is a vertical segment between points y1 and y2,
we count the number of active horizontal segments whose y coordinate is between y1 and y2, and add this
number to the total number of intersection points.
To store y coordinates of horizontal segments, we can use a binary indexed or segment tree, possibly with
index compression. When such structures are used, processing each event takes O(logn) time, so the total
running time of the algorithm is O(nlogn).
This is another example of a problem that can be solved in O(nlogn) time using a sweep line algorithm1 .
We go through the points from left to right and maintain a value d: the minimum distance between two
points seen so far. At each point, we find the nearest point to the left. If the distance is less than d, it is the
new minimum distance and we update the value of d.
If the current point is (x, y) and there is a point to the left within a distance of less than d, the x coordinate
of such a point must be between [x − d, x] and the y coordinate must be between [y− d, y+ d]. Thus, it
suffices to only consider points that are located in those ranges, which makes the algorithm efficient.
For example, in the following picture, the region marked with dashed lines contains the points that can be
within a distance of d from the active point:
246 | P a g e
The efficiency of the algorithm is based on the fact that the region always contains only O(1) points. We can
go through those points in O(logn) time by maintaining a set of points whose x coordinate is between [x −
d, x], in increasing order according to their y coordinates.
The time complexity of the algorithm is O(nlogn), because we go through n points and find for each point
the nearest point to the left in O(logn) time.
Andrew’s algorithm provides an easy way to construct the convex hull for a set of points in O(nlogn) time.
The algorithm first locates the leftmost and rightmost points, and then constructs the convex hull in two
parts: first the upper hull and then the lower hull. Both parts are similar, so we can focus on constructing
the upper hull.
First, we sort the points primarily according to x coordinates and secondarily according to y coordinates.
After this, we go through the points and add each point to the hull. Always after adding a point to the hull,
we make sure that the last line segment in the hull does not turn left. As long as it turns left, we repeatedly
remove the second last point from the hull.
The following pictures show how Andrew’s algorithm works:
247 | P a g e
40. Network Flow
40.1 Network Delay Time
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as
directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it
takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive
the signal. If it is impossible for all the n nodes to receive the signal, return -1.
248 | P a g e
40.2 Number of Operations to Make Network Connected
There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a
network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer
can reach any other computer directly or indirectly through the network.
You are given an initial computer network connections. You can extract certain cables between two directly
connected computers, and place them between any pair of disconnected computers to make them directly
connected.
Return the minimum number of times you need to do this in order to make all the computers connected. If
it is not possible, return -1.
Input: n = 6, connections = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3]]
Output: 2
Input: n = 6, connections = [[0, 1], [0, 2], [0, 3], [1, 2]]
Output: -1
Explanation: There are not enough cables.
249 | P a g e
I A R E
Enquiries: support@iare.ac.in