I took this assessment that had this prompt, and I was able to pass 18/20 tests, but not the last 2 due to hitting the execution time limit. Unfortunately, the input values were not displayed for these tests.

Prompt:

// Given an array of integers **a**, find how many of its continuous subarrays of length **m** that contain at least 1 pair of integers with a sum equal to **k**

Example:

const a = [1,2,3,4,5,6,7];
const m = 5, k = 5;
solution(a, m, k) will yield 2, because there are 2 subarrays in a that have at least 1 pair that add up to k
a[0]...a[4] - [1,2,3,4,5] - 2   3 = k ✓
a[1]...a[5] - [2,3,4,5,6] - 2   3 = k ✓
a[2]...a[6] - [3,4,5,6,7] - no two elements add up to k ✕

Here was my solution:

// strategy: check each subarray if it contains a two sum pair
// time complexity: O(n * m), where n is the size of a and m is the subarray length
// space complexity: O(m), where m is the subarray length
function solution(a, m, k) {
  let count = 0;
  for(let i = 0; i <= a.length - m; i  ){
      let set = new Set();
      
      for(let j = i; j < i   m; j  ){
          if(set.has(k - a[j])){
              count  ;
              break;
          }
          else
              set.add(a[j]);
      } 
  }
  
  return count;
}

I thought of ways to optimize this algo, but failed to come up with any. Is there any way this can be optimized further for time complexity - perhaps for any edge cases?

Any feedback would be much appreciated!

CodePudding user response：

Create a counting hash: elt -> count.

When the window moves:

1. add/increment the new element
2. decrement the departing element
3. check if (k - new_elt) is in your hash with a count >= 1. If it is, you've found a good subarray.

CodePudding user response：

• maintain a map of highest position of the last m values (add/remove/query is O(1)) and highest position of the first value of a complementary pair
• for each array element, check if complementary element is in the map, update the highest position if necessary.
• if at least m elements were processed and higest position is in the range, increase counter

O(n) overall. Python:

def solution(a, m, k):
    count = 0
    last_pos = {}  # value: last position observed
    max_complement_pos = -1
    for head, num in enumerate(a, 1):  # advance head by one
        tail = head - m
        # deletion part is to keep space complexity O(m). 
        # If this is not a concern (likely), safe to omit 
        if tail > 0 and last_pos[a[tail]] <= tail:  # time to pop last element
            del last_pos[a[tail]]
        max_complement_pos = max(max_complement_pos, last_pos.get(k-num, -1))
        count  = head >= m and max_complement_pos > tail
        last_pos[num] =head  # add element at head
    return count