Facebook Interview Question
SDE1sCountry: United States
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;
}
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;
}
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.
- axg354 April 12, 2017