DEV Community: Mohaiminul69

Solving the Two-Sum Problem: A Comprehensive Guide

Mohaiminul69 — Fri, 21 Mar 2025 08:14:04 +0000

Introduction

In this post, we will dive into the Two-Sum problem, a widely known algorithmic challenge often featured in coding interviews. The problem has two main variants, each presenting a unique twist. Let’s walk through both, explore various solutions, and learn how to solve them efficiently.

Two-Sum Problem Variants

Variant 1: Finding a Pair That Adds Up to the Target

In the first variation, you're given an array and a target number, and your goal is to determine whether any two distinct numbers from the array sum up to the target.

Example:
Let’s consider the following array and target:

arr = [2, 6, 5, 8, 11]
target = 14

The task is to find two numbers from the array that add up to 14. In this case, 6 and 8 are the pair that sums up to 14.

Approach:

If a pair is found, return True.
If no such pair exists, return False.

This variant tests whether a pair exists that satisfies the condition.

You can try out this problem using the following link.

Variant 2: Returning Indices of the Pair

In the second variant, you're given an array and a target number, but this time, your task is to return the indices of the two numbers that add up to the target.

Example:
Given the same array and target:

arr = [2, 6, 5, 8, 11]
target = 14

The output should return the indices of 6 and 8 because their sum is 14. The result will be the indices [1, 3] as arr[1] = 6 and arr[3] = 8.

You can try this problem using the following link.

Approaches to Solve the Two-Sum Problem

1. Brute Force Approach

The most straightforward way to solve the problem is through a brute force approach. This method involves iterating over all pairs of numbers in the array and checking if their sum matches the target.

Steps:

Loop through each element in the array.
For each element, loop through all subsequent elements.
Check if the sum of the two numbers equals the target.
If a pair is found, return the indices or True (depending on the problem variant).
If no pair is found after all iterations, return False (for Variant 1) or an empty result (for Variant 2).

Code Implementation:

Brute Force Approach - O(n^2) time complexity

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Complexity Analysis:

Time Complexity: O(n²), due to the nested loops.

Space Complexity: O(1), since no additional space is used.

Two-Pointers Approach for Variant 1

Another efficient approach for Variant 1 is the two-pointers technique. This approach works only if the array is sorted.

Steps:

Sort the array (if not already sorted).
Initialize two pointers:
- One at the start (left pointer)
- One at the end (right pointer)
While left < right:
- Compute sum = arr[left] + arr[right].
- If sum == target, return True.
- If sum < target, move the left pointer forward.
- If sum > target, move the right pointer backward.
- If no pair is found, return False.

Code Implementation:

Two-Pointers Approach - O(n log n) time complexity (due to sorting)

def two_sum_sorted(arr, target):
    arr.sort()  # Ensure array is sorted
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return False

Complexity Analysis:

Time Complexity: O(n log n) due to sorting, but O(n) for the two-pointer search.
Space Complexity: O(1), as no additional space is used.

2. Optimized Approach Using a Hash Map

A more efficient solution uses a hash map to store the numbers we've already seen while iterating through the array. This allows us to check if the complement (the difference between the target and the current number) exists in constant time.

Steps:

Initialize an empty hash map.
Iterate through the array:
Compute the complement: complement = target - current_number.
Check if the complement is already in the hash map.
If it is, return the indices of the current element and the complement.
Otherwise, add the current element to the hash map with its index.
If no pair is found after iterating through the entire array, return an empty result.

Complexity Analysis:

Time Complexity: O(n), since we only traverse the array once, and hash map operations are O(1) on average.
Space Complexity: O(n), as we store elements in a hash map.

C++ Implementation of the Optimized Approach

For those who prefer C++, here’s the optimized solution:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mapper;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (mapper.find(complement) != mapper.end()) 
                return {mapper[complement], i};
            mapper[nums[i]] = i;
        }
        return {};
    }
};

JavaScript Implementation of the Optimized Approach

For JavaScript developers, here's the optimized solution:

function twoSum(nums, target) {
    let mapper = new Map();
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (mapper.has(complement)) {
            return [mapper.get(complement), i];
        }
        mapper.set(nums[i], i);
    }
    return [];
}

Ruby Implementation of the Optimized Approach

For Ruby developers, here's the optimized solution:

def two_sum(nums, target)
    mapper = {}
    nums.each_with_index do |num, i|
        complement = target - num
        return [mapper[complement], i] if mapper.key?(complement)
        mapper[num] = i
    end
    []
end

Python Implementation of the Optimized Approach

The Python solution is as follows:

def two_sum(nums, target):
    mapper = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in mapper:
            return [mapper[complement], i]
        mapper[num] = i
    return []

Conclusion

Brute Force Approach: Simple but inefficient with a time complexity of O(n²). It works well for small arrays but is slow for larger inputs.

Optimized Approach with Hash Map: Improves the time complexity to O(n), making it the preferred solution for large arrays. It leverages a hash map for constant-time lookups and inserts.

The Two-Sum problem is a great example of how hash maps can optimize solutions for problems involving searching and pairing. Whether you're tackling this problem in an interview or learning algorithms, understanding time and space complexities helps in selecting the best approach.

Feel free to explore the problem further or try it yourself using the links provided:

Variant 1: Simple Two-Sum Problem

Variant 2: Two-Sum Problem with Indices

Good luck, Happy Coding!

How JWT Works

Mohaiminul69 — Thu, 30 Dec 2021 15:32:05 +0000

Nowadays we are progressing to investigate a really curious subject called JWT!! Its full form is Jason web token. So what is actually JWT, you may be wondering. Well it could be a basic however an awfully solid way of confirming a client of any JSON information. This approach is exceptionally accommodating amid two party interaction. We might need to confirm the individual whom the information is sent to. JWT saves us from the rehashed activity of sending private information on each ask. Life gets a bit easier with this.

So how does JWT work? It is fundamentally an encoded URL string that can contain any sum of information and it is made secure by making it cryptographically marked. Servers by and large utilize these tokens and they can name it as trusted as the information has been marked from the source. No other party in between can get to to it or alter it.

In any case, the information we are sending it is as it were confirming the proprietorship of the information. In case any one alters the information they can effortlessly see the information we are sending. It is since the information is serialized and the information is still not scrambled. To form the information secured we ought to scramble the information. So to overcome this circumstance it is prescribed to utilize JWT with HTTPS.

This is often how a JWT token looks after encryption. No one can adjust this let alone examine the data unless they interpret it. In spite of the fact that, we are able utilize JWT.io to interpret this data. JWT contains 3 parts: header, payload and signature. Header contains the data of the sort of ask and hashing calculation data. Payload is where all the information which we are sending. At last signature is utilized to send a mystery key. The mystery is the Signature held by the server in order to confirm tokens and sign unused ones.

We now know what JWT really is, its reason and what kind of data does JWT hold. Now lets see how the method happens Lets consider a situation where a client sends login request with there information. The server verifies the client and after that assigns it a token that contains the user's character. The token consequently is spared into neighborhood framework when that client enters the application. Presently when the client demands for anything that token is included with the ask and sent to server. The browser at that point checks for tokens and in case found confirms the client and approves the client to get to to the asked information.

This steps are continuously genuine for any kind of demands client makes interior the application. At last when the client logs out the token is removed from the nearby framework automatically. JWT makes server to server authorization simple. Be that as it may we ought to not utilize it as session token as JWT has expansive scope and there are rear ways to form botches. Besides, ready to not expel the tokens at the conclusion of the session as there's no central specialist to discredit them. We moreover should not utilize it with treats because it will increment the estimate of the overhead of the ask.

React component life cycle, and how it works

Mohaiminul69 — Thu, 30 Dec 2021 15:19:38 +0000

Each piece of code we type in incorporates a life cycle which characterizes the when execution of that code will happen. Since Respond is based on component framework where each component may be a code square and has its claim life cycle. So lets plunge to into it! By life cycle it implies that there will be a birth state, they developing state and at last the dead state. In respond there are particular terms called initialization, mounting, upgrading and unmounting separately. Amid the full life cycle different strategies are called depending on what stage the component is confronting. These strategies makes control of component easy. We as of now learnt around the four stages. Each stage have a specific list of strategies it calls upon.

Initialization phase: This is where the component gets made and it sets its props with fundamental state initialization. This courses of action are wiped out a strategy called constructor.

Mounting: This is the stage where our components gets upgraded and stacked into the browser. At that point the browser embeds it into the DOM. So this can be the phase where our component to begin with gets rendered. This is often precisely the another stage after the initialization. The overhauling may be a longer handle and so it has numerous strategies it'll call to form the vital overhauling tasks. First there's the componentWillMount strategy. It is called fair before the component is stacked
into the browser. It makes a difference the browser to induce stacked into the browser. It is way better not to call any API amid this stage as the component isn't rendered however. Since the DOM isn't prepared we clearly can not make any improvements to it. Next we have the componentDidMount strategy. This alludes the circumstance where the component is stacked into the browser. Fair some time recently this strategy render strategy is called. It gets called before long as componentWillMount is called.Then at long last the componentDidMount is called. Presently we are able make API calls and update the DOM.

Update: Another we have the overhaul stage. Amid this stage component upgrades its states and props. In the event that there's any user interaction at that point it'll lead to alter in state and props data. And due to the changes the re-rendering is additionally happens here. This can be the situation where componentShouldUpdate strategy is called. This strategies chooses whether the re-rendering will happen or not. In case it'll re-render at that point the strategy returns genuine else wrong. This choice depend on the two contentions we pass that are nextProps and nextState. Following componentWillUpdate strategy will be called some time recently re rendering. This will perform any sort of calculation some time recently severing once more. At last after the rendering is done componentDidUpdate strategy is called and it takes the prev states and props information from which the component update.

Unmounting: This is the ultimate stage of the component where component gets emptied from DOM. at first the componentWillUnMount is called. This strategy initializes the unmounting process. Th