Longest Subsequence With Limited Sum - Greedy - Sorting & Two Pointers [JS]

Description 

Solution: Greedy - Sorting & Two Pointers

It is always optimal to take the smallest numbers possible, since we want the more quantity.
Sort nums in asc order.
Sort queries in asc order and use two pointers (i = index in numsj = index in queries) to process the queries efficiently.
Move i up until it exceeds queries[j].

n = length of numsm = length of queries
Time Complexity: O(n log(n) + m log(m))
Space Complexity: O(m)

var answerQueries = function(nums, queries) {
  nums.sort((a, b) => a - b);
  queries = queries.map((query, idx) => [query, idx]).sort((a, b) => a[0] - b[0]);
  let n = nums.length, m = queries.length;
  let res = Array(m).fill(0);
  let sum = 0;
  for (let j = 0, i = 0; j < m; j++) {
    let [maxSum, index] = queries[j];
    while (i < n && sum + nums[i] <= maxSum) {
      sum += nums[i++];
    }
    res[index] = i;
  }
  return res;
};

Comments

Popular posts from this blog

Beautiful Towers II - Monotonic Increasing Stack [JS]

Check if There is a Valid Partition For The Array - Two Approaches - DP & Recursion w/ Memoization [JS]

Minimum Number of Operations to Sort a Binary Tree by Level - BFS & Cycle Counting Explained [JS]

Count Elements With Maximum Frequency - Hashmap [JS]

Mice and Cheese - Greedy w/ Sorting [JS]