How would I complete this problem in less time?

Question

EDIT: So I changed my code to the following:

function countTinyPairs(a, b, k) {
    let pairs = 0;
    let arr = [];
    b.reverse()
    for (num in a) {
        result = String(a[num]) + String(b[num])
        if (result < k) {
            pairs++
        }
    }
    return pairs
}

It works the exact same, without needing to check new arr/push, etc. Would this run in less time? Is there a way to check myself how long it takes?

I was doing a Codesignal javascript practice test (now finished). I had a really hard time, and now know that I need a lot more practice before I can even think of doing the actual test. One of the questions was:

"You are given two arrays of integers a and b of the same length, and an integer k. We will be iterating through array a from left to right, and simultaneously through array b from right to left, and looking at pairs (x, y), where x is from a and y is from b. Such a pair is called tiny if the concatenation xy is strictly less than k."

This was the code that I wrote:

function countTinyPairs(a, b, k) {
    let pairs = 0;
    let arr = [];
    b.reverse()
    for (num in a) {
        for (num in b) {
            result = String(a[num]) + String(b[num])
            if (result < k) {
                if ((arr.findIndex(e => e === result)) === -1) {
                    arr.push(String(result));
                    pairs++
                }        
            }
        }
    }
    return pairs
}

It works, except execution time limit is 4 seconds. There is a hidden test case where my function takes longer than 4 seconds to complete (I'm assuming the arrays have an extreme amount of numbers). I haven't learned anything about the Big O (or whatever it's called) yet, so I have no clue on anything about it.

I'm guessing I'd have to learn about it before I could successfully solve this problem on my own? Or, did I just write bad code and it's possible to do it with better code without knowing a thing about Big O?

Answer 1

First of all, there is no need for multiple loops. You have three:

• b.reverse() will reverse b in-place with likely O(n) complexity. Even if it's O(log n) it's still unnecessary.
• for (num in a) iterates over a in O(n).
• for (num in b) iterates over b in O(n). However, since it's an inner loop, the total is O(n^2).
• arr.findIndex(e => e === result) will trigger another O(m) iteration over any pair found. Depending on the value of k that might be only a few times or many. It's already in an O(n^2), so worst case scenario is a high value of k that covers every combination of pairs, so it will be triggered every time and thus you would get a O(n^3) complexity.

Eliminate multiple loops over a and b

Given that both a and b are of equal length, we can trivially iterate over both arrays with a single loop. To achieve reverse iteration, we can employ basic arithmetic to get the index for b that has the same distance from the end as the index of a has from the beginning. Or in other words, you can do this to iterate over both arrays at once in two directions:

const a = [2, 9, 2];
const b = [5, 3, 5];

for (let i = 0; i < a.length; i++) {
  const j = b.length - i - 1; //reverse the index for `b`
  
  console.log(`${a[i]}, ${b[j]}`);
}

Note that a.length and b.length are interchangeable, as the problem description says they are identical.

Drop the constant lookups in arr

The next problem is that arr is repeatedly being iterated over only to check the existence of a pair. Instead you can use a Set. Lookups and inserts will have sub-linear complexity by specs. Many implementations can even give you O(1). You can simplify your code to

const pairs = new Set();

/* ... if a pair is found ... */
pairs.add(result);

/* ... produce count ... */
return pairs.size;

Summary

The complete solution can look like this and you only need to iterate once through both a and b at the same time:

function countTinyPairs(a, b, k) {
  let pairs = new Set();

  for (let i = 0; i < a.length; i++) {
    const j = b.length - i - 1;
    const pair = `${a[i]}${b[j]}`;
    
    if (Number(pair) < k) {
      pairs.add(pair);
    }
  }
  
  return pairs.size;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

Alternative

This can also be expressed using array methods leading to shorter code at the cost of two loops with .map and .filter, then a third to convert to a Set:

function countTinyPairs(a, b, k) {
  let pairs = a
    .map((x, index) => `${x}${b[b.length - index - 1]}`) //produce pair
    .filter(x => Number(x) < k); //leave only tiny ones
    
  return new Set(pairs).size; //deduplicate and count
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

Using .reduce to bring it down to one loop again:

function countTinyPairs(a, b, k) {
  let pairs = a
    .reduce((acc, x, index) => {
      const pair = `${x}${b[b.length - index - 1]}`;
      if (Number(pair) < k) {
        return acc.add(pair);
      }
      return acc;
    }, new Set());
    
  return pairs.size; //deduplicate and count
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

Finally, if you hate yourself you can very make it into a single expression:

const countTinyPairs = (a, b, k) => 
  a.reduce(
    (acc, x, index) => 
      (pair => (Number(pair) < k) ? acc.add(pair) : acc)
        (`${x}${b[b.length - index - 1]}`), 
    new Set()).size;

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

No discarding of duplicates

If there is no need to remove duplicates, then the whole code becomes even simpler - you only need to maintain a count, not even collect the pairs:

function countTinyPairs(a, b, k) {
  let pairs = 0;

  for (let i = 0; i < a.length; i++) {
    const j = b.length - i - 1;
    const pair = `${a[i]}${b[j]}`;
    
    if (Number(pair) < k) {
      pairs++;
    }
  }
  
  return pairs;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

Or using array methods:

.map() + .filter()

function countTinyPairs(a, b, k) {
  let pairs = a
    .map((x, index) => `${x}${b[b.length - index - 1]}`) //produce pair
    .filter(x => Number(x) < k); //leave only tiny ones
    
  return pairs.length;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

.reduce()

function countTinyPairs(a, b, k) {
  let pairs = a
    .reduce((count, x, index) => {
      const pair = `${x}${b[b.length - index - 1]}`;
      if (Number(pair) < k) {
        return count + 1;
      }
      return count;
    }, 0);
    
  return pairs;
}

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

Single expression .reduce()

const countTinyPairs = (a, b, k) => 
  a.reduce(
    (count, x, index) => 
      count + (Number(`${x}${b[b.length - index - 1]}`) < k), 
    0);

const a = [2, 9, 2];
const b = [5, 3, 5];

console.log(countTinyPairs(a, b, 30));

Answer 2

The wording of the question is somewhat ambiguous and it doesn't help that a concrete input and expected output have not been provided. Here's how I would write the solution based on my understanding of the question -

const countTinyPairs = (a, b, k) =>
  loop
    ( ( [ x, xs ] = likeList(a)
      , [ y, ys ] = likeList([...b].reverse())
      , pairs = 0
      ) =>
      x == null || y == null
        ? pairs
        : recur
            ( xs
            , ys
            , Number(`${x}${y}`) < k
                ? pairs + 1
                : pairs
            )
    )

console.log(countTinyPairs([1,2,3,4,5], [3,4,5,6,7], 40))
// => 3

Using our own generic functions, loop, recur, and likeList, we can dramatically reduce the conceptual overhead required to derive the answer -

const likeList = (t = [], c = 0) =>
  ({ [Symbol.iterator]: _ => [ t[c], likeList(t, c + 1) ].values() })
  
const recur = (...v) =>
  ({ recur, [Symbol.iterator]: _ => v.values() })
  
const loop = (f, ...init) =>
{ let r = f(...init)
  while (r && r.recur === recur)
    r = f(...r)
  return r
}

If you'd like to learn more about the design choices for these helpers, I encourage you to see this related Q&A.

Expand the snippet below to run the program and verify the results in your own browser -

const likeList = (t = [], c = 0) =>
  ({ [Symbol.iterator]: _ => [ t[c], likeList(t, c + 1) ].values() })
  

const recur = (...v) =>
  ({ recur, [Symbol.iterator]: _ => v.values() })
  
const loop = (f, ...init) =>
{ let r = f(...init)
  while (r && r.recur === recur)
    r = f(...r)
  return r
}

const countTinyPairs = (a, b, k) =>
  loop
    ( ( [ x, xs ] = likeList(a)
      , [ y, ys ] = likeList([...b].reverse())
      , pairs = 0
      ) =>
      x == null || y == null
        ? pairs
        : recur
            ( xs
            , ys
            , Number(`${x}${y}`) < k
                ? pairs + 1
                : pairs
            )
    )
  
console.log(countTinyPairs([1,2,3,4,5], [3,4,5,6,7], 40))
// 3

---

There's room for an optimisation here. Here we introduce likeReversedList -

const likeReversedList = (t = [], c = 0) =>
  ({ [Symbol.iterator]: _ => [ t[t.length - c - 1], likeReversedList(t, c + 1) ].values() })

const countTinyPairs = (a, b, k) =>
  loop
    ( ( [ x, xs ] = likeList(a)
      , [ y, ys ] = likeList([...b].reverse())
      , [ y, ys ] = likeReversedList(b) // <-
      , pairs = 0
      ) =>
      // ...
    )

Answer 3

You are given two arrays of integers a and b of the same length. The length is the same so we need to iterate only once improving it from O(n^2) to O(n). You still need to check every element, so that is the best possible complexity for this problem.

The if statement checking for duplicates is as unneeded as the variable pairs. You can use a Set that will check for duplicates and in the end, return its length instead of counting the pairs manually.

I'm attaching the examplary solution below:

const countTinyPairs = (a, b, k) => {
        const set = new Set();
        for (let i = 0, j = b.length-1; i < a.length; i++, j--) {
                const result = String(a[i]) + String(b[j])
                if (result < k) {
                    set.add(result);
                }
        }
        return set.size;
    }

    console.log(countTinyPairs([1,2,3,4,5], [1,2,3,4,5], 40))

Edit it is not necessary to have a separate variable called j, but I thought it wad more readable having in stored in a variable.

If we don't need to check for duplicates, then it's enough to write it like this:

   const countTinyPairs = (a, b, k) => {
        let pairs;
        for (let i = 0, j = b.length-1; i < a.length; i++, j--) {
                if (String(a[i]) + String(b[j])< k) pairs++
        }
        return pairs;
    }

Answer 4

The complexity of your code is O(n^2)

Here is how I would solve it. I hope I got the task right, please post some examples of input/output.

1. If a and b are of equal length you can iterate through them with a single loop. The complexity would be O(n) where n is the length of a.

2. Why check for duplicates? Is that a requirement?

   function test(a,b,k)
   {
     let x,y,i,xy, result =[];
     for (i=0;i<a.length;i++)
     {
        x = a[i];
        y = b[b.length - 1 -i]
        xy = parseInt([x,y].join(''));
        if (xy < k) result.push(xy);
     }
     return result;
    }
    let a = [1,2,3,4,5], b=[4,5,6,7,8], k = 40;
    console.log(test(a,b,k));
   
    // Output: [18, 27, 36]