leetcode-javascript/solutions/0015-3sum.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 3sum
 * Time Complexity: O(N^2)
 * Space Complexity: O(N)
 */
var threeSum = function (arrayInput) {
  const tripletsOutput = [];
  arrayInput.sort((elementA, elementB) => elementA - elementB);

  for (let firstIndex = 0; firstIndex < arrayInput.length - 2; firstIndex++) {
    if (
      firstIndex > 0 &&
      arrayInput[firstIndex] === arrayInput[firstIndex - 1]
    ) {
      continue;
    }

    let secondPointer = firstIndex + 1;
    let thirdPointer = arrayInput.length - 1;

    while (secondPointer < thirdPointer) {
      const currentSum =
        arrayInput[firstIndex] +
        arrayInput[secondPointer] +
        arrayInput[thirdPointer];

      if (currentSum === 0) {
        tripletsOutput.push([
          arrayInput[firstIndex],
          arrayInput[secondPointer],
          arrayInput[thirdPointer],
        ]);
        secondPointer++;
        thirdPointer--;

        while (
          secondPointer < thirdPointer &&
          arrayInput[secondPointer] === arrayInput[secondPointer - 1]
        ) {
          secondPointer++;
        }
        while (
          secondPointer < thirdPointer &&
          arrayInput[thirdPointer] === arrayInput[thirdPointer + 1]
        ) {
          thirdPointer--;
        }
      } else if (currentSum < 0) {
        secondPointer++;
      } else {
        thirdPointer--;
      }
    }
  }

  return tripletsOutput;
};