Skip to main content

Leetcode 1: Two Sum

 

Leetcode Link: https://leetcode.com/problems/two-sum/

1. Problem Statement (Simple Explanation)

You are given:

  • An array of integers nums

  • An integer target

You need to return the indices of two numbers in the array such that:


Conditions:

  • Each input has exactly one solution.

  • You cannot use the same element twice.

  • You can return the answer in any order.


2. Examples

Example 1

Input:                

            nums = [2, 7, 11, 15], target = 9

Output:             

            [0, 1]

Explanation:    

            nums[0]+nums[1]=2+7=9

          So we return [0, 1].

Example 2

Input:                

            nums = [3, 2, 4], target = 6

Output:            

            [1, 2]

Explanation:    

            nums[1]+nums[2]=2+4=6

Example 3

Input:                

            nums = [3, 3], target = 6

Output:            

            [0, 1]

Explanation:    

            3+3=6


3. Approach 1 – Brute Force (Basic)

Intuition

Try all possible pairs of elements and check if their sum equals the target.

This is the most straightforward solution: two nested loops.


Algorithm (Step-by-Step)

  1. Loop i from 0 to n - 1.

  2. For each i, loop j from i + 1 to n - 1.

  3. For each pair (i, j):

    • If nums[i] + nums[j] == target, return [i, j].

  4. Since the problem guarantees exactly one solution,

            you will always find and return inside the loops.


Pseudo-code (Brute Force)



Time and Space Complexity

  • Time: O(n*n)

because we check all pairs.

  • Space: O(1)

extra space (ignoring output).


Code – Brute Force

Java code:


C code:


C++ code:


Python code:


JavaScript code:



4. Approach 2 – Optimized Using Hash Map (O(n))

Intuition

Instead of checking all pairs, we use a hash map(dictionary) to store numbers we’ve already seen and their

indices.

For each number nums[i], we check if the complement exists:

complement=target-nums[i]

  • If we have already seen complement, we found the pair.

  • Otherwise, we store nums[i] with index i in the map.

This reduces the complexity from O(n*n) to O(n).


Algorithm (Step-by-Step)

  1. Create an empty hash map valueToIndex.

  2. Loop i from 0 to n - 1:

    • Let current = nums[i].

    • Compute complement = target - current.

    • If complement is in valueToIndex:

      • return [valueToIndex[complement], i].

    • Otherwise, store valueToIndex[current] = i.

  3. Because we are guaranteed exactly one solution, the

            pair will be found during iteration.


Pseudo-code (Optimized)


Time and Space Complexity

  • Time: O(n)

because we traverse the array once, and each hash map

operation is O(1) on average.

  • Space: O(n)

to store at most n elements in the map.


Code – Optimized (Hash Map)

Java code:


C code:


C++ code:

Python code:


JavaScript code:


Comments

Post a Comment

Popular posts from this blog

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more