← Back to DSA Course | Chapter 7: Hashing | Lesson 4 of 5

Two Sum समस्या

Two Sum दो candy bars ढूंढने जैसा है जिनकी prices बिल्कुल आपके पास मौजूद पैसे तक add होती हैं। आपने जो prices देखी हैं उन्हें याद रखना partner तेज़ी से ढूंढने में मदद करता है।

In this page:

  1. Problem Idea
  2. Brute Force
  3. Hashing Approach
  4. Example Thinking
  5. Complexity
Syntax
markup 
seen = {}
for i, num in enumerate(nums):
    complement = target - num
    if complement in seen:
        return [seen[complement], i]
    seen[num] = i

Problem Idea

Two Sum आपसे किसी array में दो numbers ढूंढने को कहता है जो एक दिए target तक add होते हैं और उनकी positions return करने को कहता है। यह सबसे आम first interview questions में से एक है क्योंकि naive solution obvious है लेकिन optimal एक को time के लिए space trade करने के बारे में एक असली insight चाहिए।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	cout << "Find two numbers in the array summing to " << target;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		System.out.println("Find two numbers in the array summing to " + target);
	}
}
nums = [2, 7, 11, 15]
target = 9
print("Find two numbers in the array summing to", target)
#include <stdio.h>
int main() {
	int target = 9;
	printf("Find two numbers in the array summing to %d", target);
	return 0;
}

Brute Force

Brute-force approach दो nested loops से हर possible pair जांचता है, हर element की तुलना हर दूसरे element से करते हुए जब तक एक matching pair न मिले। इसे सही लिखना आसान है लेकिन array बढ़ने पर यह जल्दी धीमा हो जाता है, क्योंकि pairs की संख्या quadratically बढ़ती है।

उदाहरण: Brute Force

#include <iostream>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	for (int i = 0; i < 4; i++)
		for (int j = i + 1; j < 4; j++)
			if (nums[i] + nums[j] == target) cout << i << " " << j;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		for (int i = 0; i < 4; i++)
			for (int j = i + 1; j < 4; j++)
				if (nums[i] + nums[j] == target) System.out.println(i + " " + j);
	}
}
nums = [2, 7, 11, 15]
target = 9
for i in range(4):
    for j in range(i + 1, 4):
        if nums[i] + nums[j] == target:
            print(i, j)
#include <stdio.h>
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	for (int i = 0; i < 4; i++)
		for (int j = i + 1; j < 4; j++)
			if (nums[i] + nums[j] == target) printf("%d %d", i, j);
	return 0;
}

Hashing Approach

Pairs सीधे compare करने के बजाय, आप array को एक बार scan करते समय आपने पहले से देखा हर number एक hash map में store कर सकते हैं। यह 'क्या मैंने यह value पहले देखी है' को पूरे array फिर से scan करने के बजाय एक single O(1) lookup में बदल देता है।

उदाहरण: Hashing Approach

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	unordered_map<int, int> seen;
	for (int i = 0; i < 4; i++) {
		if (seen.count(nums[i])) cout << seen[nums[i]] << " " << i;
		seen[target - nums[i]] = i;
	}
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		Map<Integer, Integer> seen = new HashMap<>();
		for (int i = 0; i < 4; i++) {
			if (seen.containsKey(nums[i])) System.out.println(seen.get(nums[i]) + " " + i);
			seen.put(target - nums[i], i);
		}
	}
}
nums = [2, 7, 11, 15]
target = 9
seen = {}
for i, n in enumerate(nums):
    if n in seen:
        print(seen[n], i)
    seen[target - n] = i
#include <stdio.h>
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	int seenVal[10], seenIdx[10], count = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < count; j++) {
			if (seenVal[j] == nums[i]) printf("%d %d", seenIdx[j], i);
		}
		seenVal[count] = target - nums[i]; seenIdx[count] = i; count++;
	}
	return 0;
}

Example Thinking

हर नए number के लिए, compute करें कि इसका partner क्या होना चाहिए (target माइनस current value) और जांचें कि क्या वह partner पहले से map में है। अगर है, आपने तुरंत अपना pair ढूंढ लिया; अगर नहीं, current number को map में जोड़ें और scanning जारी रखें।

उदाहरण: Example Thinking

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	unordered_map<int, int> seen;
	for (int i = 0; i < 4; i++) {
		int partner = target - nums[i];
		if (seen.count(partner)) { cout << "Found pair at " << seen[partner] << " and " << i; break; }
		seen[nums[i]] = i;
	}
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		Map<Integer, Integer> seen = new HashMap<>();
		for (int i = 0; i < 4; i++) {
			int partner = target - nums[i];
			if (seen.containsKey(partner)) { System.out.println("Found pair at " + seen.get(partner) + " and " + i); break; }
			seen.put(nums[i], i);
		}
	}
}
nums = [2, 7, 11, 15]
target = 9
seen = {}
for i, n in enumerate(nums):
    partner = target - n
    if partner in seen:
        print("Found pair at", seen[partner], "and", i)
        break
    seen[n] = i
#include <stdio.h>
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	int seenVal[10], seenIdx[10], count = 0;
	for (int i = 0; i < 4; i++) {
		int partner = target - nums[i];
		int found = 0;
		for (int j = 0; j < count; j++) if (seenVal[j] == partner) { printf("Found pair at %d and %d", seenIdx[j], i); found = 1; break; }
		if (found) break;
		seenVal[count] = nums[i]; seenIdx[count] = i; count++;
	}
	return 0;
}

Complexity

Brute-force pair check को O(n²) time लगता है क्योंकि हर element की तुलना हर दूसरे से होती है। Hashing approach इसे seen values store करने के लिए O(n) extra space से trade करता है, typical running time को O(n) तक लाते हुए।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	int n = 1000;
	long bruteForceOps = (long)n * n;
	long hashingOps = n;
	cout << "Brute force: O(n^2) = " << bruteForceOps << " ops\n";
	cout << "Hashing: O(n) = " << hashingOps << " ops";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int n = 1000;
		long bruteForceOps = (long) n * n;
		long hashingOps = n;
		System.out.println("Brute force: O(n^2) = " + bruteForceOps + " ops");
		System.out.println("Hashing: O(n) = " + hashingOps + " ops");
	}
}
n = 1000
brute_force_ops = n * n
hashing_ops = n
print("Brute force: O(n^2) =", brute_force_ops, "ops")
print("Hashing: O(n) =", hashing_ops, "ops")
#include <stdio.h>
int main() {
	long n = 1000;
	long bruteForceOps = n * n;
	long hashingOps = n;
	printf("Brute force: O(n^2) = %ld ops\n", bruteForceOps);
	printf("Hashing: O(n) = %ld ops", hashingOps);
	return 0;
}
Related Topics

Prefix Sum क्या है · N-Queens समस्या · दो Sorted Lists को Merge करना · Two Pointer तकनीक

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. nums[i] + nums[i] == target जांचना और उसी element को दो बार reuse करना, जब हर index सिर्फ एक बार उपयोग हो सकता है।
  2. Current number को इसके complement जांचने से पहले map में insert करना, जो एक element को खुद के साथ pair कर सकता है।
  3. Final solution के रूप में दो nested loops उपयोग करना, जो O(n^2) है जब एक hash map O(n) देता है।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Collision Handling Next Lesson → Frequency Counting

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.