Category: sort_and_search
-
LeetCode 1885: Count Pairs in Two Arrays
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…
-
LeetCode 2089: Find Target Indices After Sorting Array
link Sort around pivot = target and along the way discover the range containing target. Time: , space: .
-
LeetCode 2389: Longest Subsequence With Limited Sum
link If we had nums sorted, we could compute its list of cumulative sums. For a query, its insert position in this list of cumulative sums would give the max length of subsequence for that query. Time: . Space: .
-
LeetCode 1385: Find the Distance Value Between Two Arrays
link For each element from arr1 try against all elements in arr2. If arr1 has elements and arr2 has elements, time: , space: . Insight: For a number in nums1, if the closest number in nums2 is and , then all other numbers in nums2 must also be more than distance away from . If…
unreasonably effective 