• -2

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(n^2) time and O(n) extra space complexity. The space for the solution can itself be O(n^3) for the case where all numbers are same and any triplet sums to the required sum.

The strategy is to use index sorting and then apply a 2sum approach.

``````/* 2Sum helper which returns indexes of 2 elements with sum 'sum' - O(n) */
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<pair<int,int>> twoSum(vector<int>& nums, vector<int>& idx, int start, int end, int sum) {
vector<pair<int,int>> res;
while(start < end){
int n1 = nums[idx[start]];
int n2 = nums[idx[end]];

if(n1+n2 == sum) {
vector<int> start_idx;
while(start < end && nums[idx[start]] == n1) {
start_idx.push_back(start);
start++;
}
vector<int> end_idx;

while(end >= start && nums[idx[end]] == n2) {
end_idx.push_back(end);
end--;
}
for(const auto& i1 : start_idx) {
for(const auto& i2 : end_idx) {
res.push_back({idx[i1],idx[i2]});
}
}
}
else if(n1+n2 < sum) {
start++;
}
else {
end--;
}
}
return res;
}

vector<vector<int>> threeSum(vector<int>& nums, int sum) {
int n = nums.size();
if(n < 3) return {};
vector<vector<int>> res;
vector<int> idx(n);

for(int i = 0; i < n; i++) idx[i] = i;

/* index sorting */
std::sort(idx.begin(), idx.end(), [&](int a, int b){
return nums[a] < nums[b];
});

for(int i = 0; i < n-2; i++){
auto temp = twoSum(nums, idx, i+1, n-1, sum - nums[idx[i]]);
for(const auto& el : temp){
res.push_back({idx[i], el.first, el.second});
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(n^2) time and O(n) extra space complexity. The space for the solution can itself be O(n^3) for the case where all numbers are same and any triplet sums to the required sum.

The strategy is to use index sorting and then apply a 2sum approach.

``````/* 2Sum helper which returns indexes of 2 elements with sum 'sum' - O(n) */
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<pair<int,int>> twoSum(vector<int>& nums, vector<int>& idx, int start, int end, int sum) {
vector<pair<int,int>> res;
while(start < end){
int n1 = nums[idx[start]];
int n2 = nums[idx[end]];

if(n1+n2 == sum) {
vector<int> start_idx;
while(start < end && nums[idx[start]] == n1) {
start_idx.push_back(start);
start++;
}
vector<int> end_idx;

while(end >= start && nums[idx[end]] == n2) {
end_idx.push_back(end);
end--;
}
for(const auto& i1 : start_idx) {
for(const auto& i2 : end_idx) {
res.push_back({idx[i1],idx[i2]});
}
}
}
else if(n1+n2 < sum) {
start++;
}
else {
end--;
}
}
return res;
}

vector<vector<int>> threeSum(vector<int>& nums, int sum) {
int n = nums.size();
if(n < 3) return {};
vector<vector<int>> res;
vector<int> idx(n);

for(int i = 0; i < n; i++) idx[i] = i;

/* index sorting */
std::sort(idx.begin(), idx.end(), [&](int a, int b){
return nums[a] < nums[b];
});

for(int i = 0; i < n-2; i++){
auto temp = twoSum(nums, idx, i+1, n-1, sum - nums[idx[i]]);
for(const auto& el : temp){
res.push_back({idx[i], el.first, el.second});
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(n^2) time and O(n) extra space complexity. The space for the solution can itself be O(n^3) for the case where all numbers are same and any triplet sums to the required sum.

The strategy is to use index sorting and then apply a 2sum approach.

``````/* 2Sum helper which returns indexes of 2 elements with sum 'sum' - O(n) */
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <unordered_map>

using namespace std;

vector<pair<int,int>> twoSum(vector<int>& nums, vector<int>& idx, int start, int end, int sum) {
vector<pair<int,int>> res;
while(start < end){
int n1 = nums[idx[start]];
int n2 = nums[idx[end]];

if(n1+n2 == sum) {
vector<int> start_idx;
while(start < end && nums[idx[start]] == n1) {
start_idx.push_back(start);
start++;
}
vector<int> end_idx;

while(end >= start && nums[idx[end]] == n2) {
end_idx.push_back(end);
end--;
}
for(const auto& i1 : start_idx) {
for(const auto& i2 : end_idx) {
res.push_back({idx[i1],idx[i2]});
}
}
}
else if(n1+n2 < sum) {
start++;
}
else {
end--;
}
}
return res;
}

vector<vector<int>> threeSum(vector<int>& nums, int sum) {
int n = nums.size();
if(n < 3) return {};
vector<vector<int>> res;
vector<int> idx(n);

for(int i = 0; i < n; i++) idx[i] = i;

/* index sorting */
std::sort(idx.begin(), idx.end(), [&](int a, int b){
return nums[a] < nums[b];
});

for(int i = 0; i < n-2; i++){
auto temp = twoSum(nums, idx, i+1, n-1, sum - nums[idx[i]]);
for(const auto& el : temp){
res.push_back({idx[i], el.first, el.second});
}
}
return res;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.