Category: sort_and_search
-
LeetCode 2554. Maximum Number of Integers to Choose From a Range I
link Dynamic Programming The problem can be thought as Knapsack Without Repeat problem where items are in , capacity is , and value of each item is . Time: , space: same. Since a subproblem depends only on subproblems from the previous row, we can reuse two rows. Time: , space: . Greedy Since all…
-
LeetCode 1099: Two Sum Less Than K
link Sorting and two pointers Time: that of sorting, . Space: that of sorting. Counting sort and two pointers Time: , space: . Use dict to store count. We need to sort the keys only. If range of values in nums is . Time: , space: .
-
LeetCode 354: Russian Doll Envelopes
link Longest Increasing Subsequence: Dynamic Programming We need to find the largest subset of envelopes which can be ordered as an increasing sequence. Sorting by width, makes it the problem of finding the length of longest increasing subsequence. Time: , space: . Longest Increasing Subsequence: Binary Search Once we sort the envelopes by width, the…
-
LeetCode 1889: Minimum Space Wasted From Packaging
link Sort and linear search For each supplier we can find the minimum waste by trying to fit a package in the smallest box possible. We take min across all suppliers. If the longest box list has length , then time: . Space: that of sorting. Sort and binary search In min_waste_for_supplier(), instead of trying…
-
LeetCode 719: Find K-th Smallest Pair Distance
link All pairs with max heap Generate all possible pairs keeping smallest in a max heap. Time: , space: Sorting and minq We want to generate the pairs in sorted order of distance. Sort nums, put pairs having different first elements in a minq. These are like heads of sorted linked lists. Now pop times…
-
LeetCode 1552: Magnetic Force Between Two Balls
link We recast the problem of maximizing the minimum force into the problem: Given the sequence of minimum forces , what is the rightmost value that is achievable. To search the rightmost value, we perform binary search in the range [1, ]. In each iteration of the binary-search, we check, for a given value of…
-
LeetCode 1508: Range Sum of Sorted Subarray Sums
link Brute Force We can generate all sums in time. Sort them in time. Then, return (right-left+1) of them in [left : right+1]. Time would be . Generate sums in sorted order If we could generate the sub-array sums one at a time in sorted order, we could generate first (left-1) of them and throw…
-
LeetCode 1300: Sum of Mutated Array Closest to Target
link Brute Force We need to find the best defined as: . We break a tie in favor of smaller . Since all numbers in arr are positive integers, the domain of is . Time: , space: . Sort and search We can break the inner sum to get rid of like: . In the…
-
LeetCode 2602. Minimum Operations to Make All Array Elements Equal
link Brute force For query , number of ops is . Time: , space: . Sort and search If , we can remove the . Then, number of ops is . So, for each , we can find the number of ops in time. Similarly, if , the number of ops, , can be found…
-
LeetCode 611: Valid Triangle Number
link A triplet is a 3-element subset like . Therefore, different ordering of the three elements does not make a different triplet. In other words, all six permutations of the three elements are counted as the same triplet. A triplet is trianglular if the three numbers in it respect the geometric triangular property: sum of…
unreasonably effective 