unreasonably effective

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…

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…

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…

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…

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…

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…

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…

link Brute Force Check sum1 > sum2 Time: , space: . Check diff1 + diff2 > 0 We check against a modified version of the inequality: (nums1[i] – nums2[i]) + (nums1[j] – nums2[j]) > 0. An important difference is that outer loop is only handling the index i and the inner loop is only handling…

link Sort around pivot = target and along the way discover the range containing target. Time: , space: .