Sum Closest To Given Number 🚧

Given a 3 x 3 matrix, find if there exists a sum of numbers from each row that adds up to a given number such as 0.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[
  [1, 0 , 3],
  [0, 5, 0],
  [1, 1, 0]
]
True because 0 + 0 + 0

[
  [1, -3 , 3],
  [3, 8, 0],
  [1, 1, 0]
]
True because -3 + 3 + 0


[
  [1, -33 , 3],
  [31, 8, 0],
  [1, 1, 0]
]
False

Analysis

  • brute force approach would mean that we have cubic time complexity, so that is not so good
  • there is no restriction on sorting, so we could sort the arrays, say in descending order
    • this gives us the largest numbers towards left and smallest towards right

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[
  [1, 0 , 3],
  [0, 5, 0],
  [1, 1, 0]
]

After sorting we get
[
  [3, 1 , 0],
  [5, 0, 0],
  [1, 1, 0]
]


Let's say we have three indices i, j and k

i,j,k starts at 0

matrix[0][i] => 3
matrix[0][j] => 5
matrix[0][k] => 1

The approach I thought of and was recomended was to try and find a O(n^2) alternative, since this is one of those problems that is not possoible to do in better time. The way we can do this is to recognize that we are looking for a sum of three numbers (one from each row) and that can be either 0 or less than 0 or more than 0. If we simply pick each element in derial order that degenerates into cubic complexity. But what if we sorted each row. Let’s take an example:

1
2
3
4
5
[
  [-3, 1 , 0],
  [5, 0, 0],
  [1, 1, 0]
]

Similar

Leetcode seems to have a similar problem here

Attempt

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
          }
          if (nums[i]+nums[j+1]+nums[k] > sum) {
            k = k - 1;
          } else {
            j = j + 1;
          }
        }
        //if (nums[i+1] == nums[i])
      }
      return res;
    }
};

This fails the test case because we are allowing duplicates when we shouldn’t.

1
2
3
4

Input: [0,0,0,0]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Expected: [[0,0,0]]

Second ATtempt

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i > 0 && nums[i] == nums[i-1]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;

            j++;
            k--;
          }
          if (nums[i]+nums[j+1]+nums[k] > sum) {

            k = k - 1;

          } else {
            j = j + 1;
          }
        }
      }
      return res;
    }
};

This has a side effect and fails the following test case

1
2
3
Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2]]
Expected: [[-1,-1,2],[-1,0,1]]

Third Attempt

The condition (nums[i]+nums[j+1]+nums[k] > sum should be in an else if

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i > 0 && nums[i] == nums[i-1]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (nums[i]+nums[j+1]+nums[k] > sum) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

However, this fails the testcase

1
2
3
Input: [1,-1,-1,0]
Output: []
Expected: [[-1,0,1]]

Fourth

The issue is that since we are sorting in ascending order and we have the check to skip duplicates of nums[i], we end up skipping all the -1’s!
We need to modify that check a bit.

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i+1 < nums.size() && nums[i] == nums[i+1]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (nums[i]+nums[j+1]+nums[k] > sum) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

But this fails

1
2
3
4

Input: [-1,0,1,2,-1,-4]
Output: [[-1,0,1]]
Expected: [[-1,-1,2],[-1,0,1]]

Ah this brings us back to the previous failure.

I think I misunderstood. The only duplicates we should skips for nums[i] are 0’s?

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end(), [](int a, int b) { return a < b;});
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i] if 0
        if (i+1 < nums.size() && nums[i] == 0 && nums[i+1] == 0) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (nums[i]+nums[j+1]+nums[k] > sum) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

Revising core logic

The main comparison logic is somewhat flawed. We need to check if sum is equal to 0, greater than 0 or less than 0. The reason fos this is that

Accepted Solution

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      if (nums.size() < 3) return res;
      sort(nums.begin(), nums.end());
      for (int i = 0; i < nums.size() - 2; i++) {
        // skip duplicates of nums[i]
        if (i > 0  && nums[i-1] == nums[i]) { continue; }
        int j = i + 1;
        int k = nums.size() - 1;
        while (j < k) {
          int sum = nums[i]+nums[j]+nums[k];
          if (sum == 0) {
            res.push_back({nums[i], nums[j], nums[k]});
            // skip all duplicates for nums[j] and nums[k]
            while (j < k && nums[k-1] == nums[k]) k--;
            while (j < k && nums[j+1] == nums[j]) j++;
            j++;
            k--;
          } else if (sum > 0) {
            k--;
          } else {
            j++;
          }
        }
      }
      return res;
    }
};

Leetcode similar problem