Thread by @_MohitBalwani

Day 2 of #100DaysOfCode

PROBLEM NAME - 3 SUM

Given an array of integers "nums" and an integer "target", find all possible indices of triplets such that they add up to target.

A thread 🧵👇

Approach - 1 : Brute Force

Use 3 "for loops" and check for all possible triplets of numbers that makes the target sum.

Time Complexity - O(n^3)
Space Complexity - O(1)

2nd and 3rd approaches requires knowledge of HashMap and 2 pointers that I discussed in the 2SUM problem in my previous thread.

Here is the thread in which I covered those topics so give it a read before proceeding further!

https://twitter.com/_MohitBalwani/status/1538224876091494400?s=20&t=WBPR0-UCILmBAekwWPgd4g

Approach - 2 : Using HashMap

- Go to each element of the array and use the HashMap Approach to find the pair of 2 numbers from the rest of the array.

- Refer to my Day 1 thread to know more about the HashMap Approach

Time Complexity - O(n^2)
Space Complexity - O(n)

Approach - 3 : Sorting + 2 pointers (Most Optimal)

- Sort the array

- Go to each element of the array and use the 2 pointers approach to find the other pairs from the rest of the array.

- Refer to my Day 1 thread to know more about the 2 pointers approach.

Time Complexity - O(n^2)
Space Complexity - O(1)

I hope you guys understood all the approaches to solve this problem! Consider retweeting if it helped.

I will be sharing much more problems in the upcoming days so make sure you follow along @_MohitBalwani !