Interview Question | 3Sum Problem| Array | C++

7 min readNov 15, 2023

Interview Question | 3Sum Problem| Array | C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin() , nums.end());    //Sorted Array
        if(nums.size() < 3){    //Base case 1
            return {};
        }
        if(nums[0] > 0){        //Base case 2
            return {};
        }
        vector<vector<int>> answer;
        for(int i = 0 ; i < nums.size() ; ++i){     //Traversing the array to fix the number.
            if(nums[i] > 0){     //If number fixed is +ve, stop there because we can't make it zero by searching after it.
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]){    //If number is getting repeated, ignore the lower loop and continue.
                continue;
            }
            int low = i + 1 , high = nums.size() - 1;   //Make two pointers high and low, and initialize sum as 0.
            int sum = 0;
            while(low < high){                          //Search between two pointers, just similiar to binary search.
                sum = nums[i] + nums[low] + nums[high];
                if(sum > 0){   //If sum is +ve, means, we need more -ve numbers to make it 0, decreament high (high--).
                    high--;
                } else if(sum < 0){ //If sum is -ve, means, we need more +ve numbers to make it 0, increament low (low++).
                    low++;
                } else {
                    answer.push_back({nums[i] , nums[low] , nums[high]});  //we have found the required triplet, push it in answer vector
                    int last_low_occurence = nums[low] , last_high_occurence = nums[high];  //Now again, to avoid duplicate triplets, we have to navigate to last occurences of num[low] and num[high] respectively
                    while(low < high && nums[low] == last_low_occurence){   // Update the low and high with last occurences of low and high.
                        low++;
                    }
                    while(low < high && nums[high] == last_high_occurence){
                        high--;
                    }
                }
            }
        }
        return answer;      //Return the answer vector.
    }
};

English :

This C++ code defines a class named Solution with a public member function threeSum. The purpose of the threeSum function is to find all unique triplets in an array that add up to zero.

Here’s a step-by-step explanation of the code:

Sorting the Array:

sort(nums.begin(), nums.end());

The input vector nums is sorted in ascending order. Sorting is a crucial step in this algorithm.

Base Cases:

if (nums.size() < 3) { return {}; } if (nums[0] > 0) { return {}; }
If the size of the array is less than 3, it’s not possible to form triplets, so an empty vector is returned.
If the smallest element in the sorted array is greater than zero, it’s not possible to form triplets with a sum of zero, so an empty vector is returned.

Main Loop:

for (int i = 0; i < nums.size(); ++i) {

This loop iterates through the sorted array to fix one number at a time.

Handling Positive Fixed Number:

if (nums[i] > 0) { break;

If the fixed number is positive, the loop is terminated because it’s not possible to make a sum of zero by searching after it.

Ignoring Repeated Numbers

if (i > 0 && nums[i] == nums[i - 1]) { continue;

If the fixed number is the same as the previous one, it skips the current iteration to avoid duplicate triplets.

Two-Pointer Approach:

int low = i + 1, high = nums.size() - 1; int sum = 0; while (low < high) {
Two pointers (low and high) are initialized, and a sum variable is set to 0.
The algorithm uses a two-pointer approach to search for triplets.

Updating Pointers Based on Sum:

if (sum > 0) { high--; } else if (sum < 0) { low++;
If the sum is positive, the high pointer is decremented.
If the sum is negative, the low pointer is incremented.
} else { answer.push_back({nums[i], nums[low], nums[high]});

If a triplet is found, it is added to the answer vectors.

int last_low_occurrence = nums[low], last_high_occurrence = nums[high]; while (low < high && nums[low] == last_low_occurrence) { low++; } while (low < high && nums[high] == last_high_occurrence) { high--; }

To avoid duplicate triplets, the low and high pointers are updated to their last occurrences

return answer

The function returns the vector of unique triplets that add up to zero.

This algorithm efficiently finds triplets using a combination of sorting and a two-pointer approach, ensuring that duplicate triplets are avoided.

Hindi :

यह C++ कोड एक Solution नामक कक्षा को परिभाषित करता है जिसमें एक सार्वजनिक सदस्य फ़ंक्शन threeSum है। threeSum फ़ंक्शन का उद्देश्य ऐसे सभी अद्वितीय तिगुनात्मकों को खोजना है जो एक सरणि में जोड़ कर जीरो बनाते हैं। इस कोड का चरण-बंधन विवरण इस प्रकार है: सरणि को क्रमबद्ध करना:

sort(nums.begin(), nums.end());

इनपुट वेक्टर nums को आरोही क्रम में क्रमबद्ध किया जाता है। क्रमबद्ध करना इस एल्गोरिदम में एक महत्वपूर्ण कदम है। मौलिक मामले:

if (nums.size() < 3) { return {}; } if (nums[0] > 0) { return {}; }

यदि सरणि का आकार 3 से कम है, तो तिगुनात्मक बनाना संभावनहीन है, इसलिए एक खाली वेक्टर लौटाया जाता है।
यदि क्रमबद्ध सरणि में सबसे छोटा तत्व शून्य से अधिक है, तो शून्य की योग से तिगुनात्मक बनाना संभावनहीन है, इसलिए एक खाली वेक्टर लौटाया जाता है। मुख्य लूप:

for (int i = 0; i < nums.size(); ++i) {

यह लूप क्रमबद्ध सरणि में एक समय में एक संख्या को ठीक करने के लिए चलता है। सकारात्मक ठीक किए गए संख्या का संबोधन:

if (nums[i] > 0) { break;

यदि ठीक की गई संख्या सकारात्मक है, तो लूप समाप्त हो जाता है क्योंकि इसके बाद खोज करने से शून्य का योग संभावनहीन है। दोहरी संख्याएँ नजरअंदाज करना

if (i > 0 && nums[i] == nums[i - 1]) { continue;

यदि ठीक की गई संख्या पिछली संख्या के समान है, तो यह वर्तमान पुनरावृत्ति को छोड़ता है ताकि डुप्लिकेट तिगुनात्मकों से बचा जा सके। दो-पॉइंटर दृष्टिकोण:

int low = i + 1, high = nums.size() - 1; int sum = 0; while (low < high) {

दो पॉइंटर्स (low और high) की शुरुआत की जाती है, और एक संबंधित सूची को 0 पर सेट किया जाता है।
इस एल्गोरिदम में तिगुनात्मक खोजने के लिए एक दो-पॉइंटर दृष्टिकोण का उपयोग किया जाता है। संबंधित सूची पर आधारित पॉइंटर अपडेट करना:

if (sum > 0) { high--; } else if (sum < 0) { low++;

यदि सूची सकारात्मक है, तो high पॉइंटर को कम किया जाता है।
यदि सूची नकारात्मक है, तो low पॉइंटर को बढ़ाया जाता है।

} else { answer.push_back({nums[i], nums[low], nums[high]});

यदि एक तिगुनात्मक मिल जाता है, तो इसे उत्तर वेक्टर में जोड़ा जाता है।

int last_low_occurrence = nums[low], last_high_occurrence = nums[high]; while (low < high && nums[low] == last_low_occurrence) { low++; } while (low < high && nums[high] == last_high_occurrence) { high--; }

डुप्लिकेट तिगुनात्मकों से बचने के लिए, low और high पॉइंटर्स को उनके आखिरी प्रकटियों पर अपडेट किया जाता है।

return answer

फ़ंक्शन विशेषता तिगुनात्मक लौटाता है जो शून्य पर जोड़ करने वाले अद्वितीय तिगुनात्मकों का वेक्टर है। यह एल्गोरिदम सॉर्टिंग और एक दो-पॉइंटर दृष्टिकोण का संयोजन करके समझदारी से तिगुनात्मकों को खोजता है, सुनिश्चित करता है कि डुप्लिकेट तिगुनात्मकों से बचा जाता है।

Hinglish :

Is C++ code mein ek class ‘Solution’ define ki gayi hai jismein ek public member function ‘threeSum’ hai. Is ‘threeSum’ function ka uddeshya hai ki ek aise array mein saare vishesht triplets dhoondhe jaayein jo zero ke barabar hote hain.

Yahaan ek kadam-se-kadam vyakhya di gayi hai:

Array Ko Sort Karna:

sort(nums.begin(), nums.end());

Input vector ‘nums’ ko chadhne-khulne order mein sort kiya jaata hai. Is algorithm mein sorting ek mahatva purna kadam hai.

Base Cases:

if (nums.size() < 3) { return {}; } if (nums[0] > 0) { return {}; }

Agar array ka size 3 se chhota hai, toh triplets banane mein sambhav nahi hai, isliye ek khali vector return kiya jaata hai.
Agar sort kiye gaye array ka sabse chhota element zero se bada hai, toh zero ke sum ke triplets banane mein sambhav nahi hai, isliye ek khali vector return kiya jaata hai.

Main Loop:

for (int i = 0; i < nums.size(); ++i) {

Yeh loop sort kiye gaye array mein ek samay par ek number ko fix karne ke liye iterate karta hai.

Positive Fixed Number Ko Handle Karna:

if (nums[i] > 0) { break;

Agar fix kiya gaya number positive hai, toh loop ko khatam kar diya jaata hai kyun ki iske baad search karke zero ka sum nahi banaya ja sakta.

Dohri Sankhyaon Ko Ignore Karna:

if (i > 0 && nums[i] == nums[i - 1]) { continue;

Agar fix kiya gaya number pichle number ke barabar hai, toh vartaman iteration ko chhod diya jaata hai taaki dohre triplets se bacha ja sake.

Do-Pointer Approach:

int low = i + 1, high = nums.size() - 1; int sum = 0; while (low < high) {

Do pointers (‘low’ aur ‘high’) ko shuru mein initialize kiya jaata hai, aur ek sum variable ko zero set kiya jaata hai.
Is algorithm mein do-pointer approach ka istemaal triplets dhoondhne ke liye hota hai.

Sum Ke Aadhar Par Pointers Ko Update Karna:

if (sum > 0) { high--; } else if (sum < 0) { low++;

Agar sum positive hai, toh ‘high’ pointer ko ghata diya jaata hai.
Agar sum negative hai, toh ‘low’ pointer ko bada diya jaata hai.

} else { answer.push_back({nums[i], nums[low], nums[high]});

Agar ek triplet milta hai, toh use ‘answer’ vector mein daal diya jaata hai.

Dohre Triplets Ko Bachane Ke Liye:

int last_low_occurrence = nums[low], last_high_occurrence = nums[high]; while (low < high && nums[low] == last_low_occurrence) { low++; } while (low < high && nums[high] == last_high_occurrence) { high--;

Dohre triplets ko bachane ke liye, ‘low’ aur ‘high’ pointers ko unke aakhiri milne waale sthal par update kiya jaata hai.

Answer Ko Vapas Karna:

return answer;

Function vishesht triplets ka vector return karta hai jo zero ke barabar hote hain.

Yeh algorithm sorting aur do-pointer approach ka sahi dhang se istemaal karta hai, jisse duplicate triplets ko bachaya ja sake.

Interview Question | 3Sum Problem| Array | C++

English :

Hindi :

Hinglish :

Written by Kartikeya Mishra

No responses yet