Leetcode Problem 1000-1099

1010. Pairs of Songs With Total Durations Divisible by 60 🌟🌟

Brute force (TLE)

• We can find all the pairs from the time array which are divisible by 60
• TC: O(N^2)
• SC: O(1)

Hashing Solution

• t % 60 gets the remainder from 0 to 59.
• We count the occurrence of each remainders in a array/hashmap mp.
• we want to know that, for each t in time,
• how many x satisfy (t + x) % 60 = 0.
• The straight forward idea is to take x % 60 = 60 - (t % 60), which is valid for the most cases.
• But, if t % 60 = 0 then x % 60 should be 0 instead of 60.
• there are two solutions to avoid this situation,
  • x % 60 = (60 - t % 60) % 60,
  • x % 60 = (600 - t) % 60.
• TC: O(N), Single for loop
• SC: O(N), for the extra space to store the remainders.

---

1029. Two City Scheduling 🌟🌟

sorting + greedy solution

• sort the costs by the difference between a and b.
• add A’s cost in first half and B’s cost in second half.
• return the ans.
• TC: O(nlogn)
• SC: O(1)

---

1041. Robot Bounded In Circle 🌟🌟

Simulation

• We can simulate the robots movement 4 times and check if it reaches to same location(0,0), if it does return true, else false. or
• we can simulate the process 1 time and check if it reaches to same location(0,0) or it changed its directions, if it does return true, else false.
• TC: O(N)
• SC: O(1)

---

1081. Smallest Subsequence of Distinct Characters 🌟🌟

---

1094. Car Pooling 🌟🌟

Approach

• for every trip we add the passengers in the car from destination and drop them off to the destination.
• After these actions we check in our stops array(hashmap) if the car has enough empty seats.
• If it does return true, else we return false.

---