PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

3 SUM problem

(1 votes, average: 1.00 out of 5)

March 27, 2013 by puzzler Leave a Comment

Problem Statement:
Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.

Solution:
Brute force approach is of O(n^4) but we can solve it in O(n^2) by using the approach in Non duplicate pairs that sum to S.

First sort the array(Order O(nlogn)), than finding a, b, c pairs is equal to finding=> For every element a in the array, if there exists a pair with sum equal to -a. As explained in Non duplicate pairs that sum to S, we can get the pair with sum -a in O(n) and we have to repeat this exercise n times so order of complexity will be O(n^2).

  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments
Next Puzzle
Find a pythagorean triplet from an array

Checkout more Interview Questions Tags: Algorithm, Array, Difficult, Interview, Solved Puzzles

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Find a pythagorean triplet from an array
  • Falling Diamonds Solution: Google codejam 2013 Round 1B
  • Beautiful Strings solution: Facebook hacker Cup 2013 Qual Round
  • Three blue and two red hats puzzle
  • RoboElection solution: Facebook hacker cup 2013 Round 2
  • Full Binary Tree Solution – Google Code Jam
  • Reverse a link list without using another
  • Subjective Question set C/C++ – Part 1
  • Swap two integer variables
  • Objective Questions set C/C++ – Part 2

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2025 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▲
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous