Sum of Pair Equal to Target in Array
In the context of analyzing data within arrays, it's often necessary to determine whether two or three different elements in the array sum up to a specific target value. This problem is a common one in programming, especially in scenarios involving searching for pairs or triplets of numbers that meet a particular condition in most of scenarios we are asked to find a target sum, product…etc
Given an array of integers, we need to check if there exist two distinct elements in the array such that their sum equals a given target value. If such a pair exists, the function should print true; otherwise, it should print false.
Example
Input: nums: [2, 7, 11, 15], target: 9
Output: true
Explanation: In this case, the elements 2 and 7 sum up to 9, so the function should print true.
Input: nums: [2, 9, 11, 9, 4], target: 18
Output: true
Explanation: In this case, the elements 9(at index 1) and 9(at index 3) sum up to 18, both elements are at different index so the function should print true.
Approach
To solve this problem, we want 2 numbers from the array to check whether their sum satisfies the target.
How can we get those two numbers?
To find the pair of numbers that satisfies the target condition, we need to check all possible pairs in the array. If we find any pair that meets the condition, we can conclude that such a pair exists and the answer will be true. So, Let's think about how we can systematically check each pair of elements in the array. We can imagine iterating through each element in the array and checking it against every other element to see if their sum equals the target.
Detailed Explanation
So we can say, we want a pair, which sums to target can be written asFirst Element + Second Element = Target
Selecting the First Element: We start by selecting the first element of the array. Let’s say our array is nums = [2, 7, 11, 15]. The first element is 2.
Selecting the Second Element: Next, we look at each of the other elements in the array to see if adding any of them to 2 gives us the target sum. Since, we have to consider different elements (their values can be same but their positions can’t be same), so the index of the first element cant be the same as the second element so we don’t consider those indexes.
- At index 0, Since index of 2 is 0 so we won't consider index 0.
- At index 1, Add 2 and 7 → 2 + 7 = 9 (This matches our target! We can immediately print true here.)
- If we didn’t find a match, we’d continue:
- At index 3, Add 2 and 11 → 2 + 11 = 13 (Not the target)
- At index 4, Add 2 and 15 → 2 + 15 = 17 (Not the target)
If we didn’t find a matching pair with 2, we’d move on to the next element as our new "first" element, which is 7, and repeat the process of finding the second element fixing our first element as 7.
In this way, we will be able to consider all possible pairs. After all iterations, we can simply print false, as we would be sure that no such pair exists that satisfies the target. If such a pair had existed, the function would have already returned after printing true.
How can we consider all pairs via Code?
The answer to this is by using nested loop (Loop inside a loop), the first loop is the outer loop and the second loop is the inner loop
- Outer Loop: This loop selects the first element of the pair. For every position of this first element, we need to find the second element.
- Inner Loop: This loop finds the second element to pair with the current first element. It skips that index which is the current index of the outer loop to avoid pairing an element with itself. Within the inner loop, we check if the sum of the elements selected by the outer and inner loops equals the target value.
Dry Run
Input Details
- Array: nums[] = {2, 7, 11, 15}
- Size of the array (n): 4
- Target sum: 9
Outer Loop Iteration (Variable i)
The outer loop starts with i = 0. This loop selects the first number (nums[i]) for checking.
Outer Loop i = 0
- First number: nums[i] = nums[0] = 2
Inner Loop Iteration (Variable j)
The inner loop starts with j = 0. This loop checks every other number against nums[i].
- Inner Loop j = 0
- nums[j] = nums[0] = 2
- Since i == j, this iteration is skipped.
- Inner Loop j = 1
- nums[j] = nums[1] = 7
- Check: nums[i] + nums[j] = 2 + 7 = 9
- The sum equals the target (9).
- Output true and return from the function.
Function Ends
Since a pair (2, 7) that sums up to the target (9) is found, the program exits early without checking further pairs.
Output
The output is: true
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to check if any two numbers sum up to the target
void hasPairWithSum(int nums[], int n, int target) {
// Outer loop: iterates through each element as the first element of the pair
for (int i = 0; i < n; ++i) {
// Inner loop: iterates through each element as the second element of the pair except the first element
for (int j = 0; j < n; ++j) {
// If the indexes are the same, skip
if (i == j) continue;
// Check if the sum of nums[i] and nums[j] equals the target
if (nums[i] + nums[j] == target) {
// Print true if such a pair is found and return
cout << "true";
return;
}
}
}
// Print false if no such pair is found after checking all pairs
cout << "false";
}Java
import java.util.Scanner;
public class LearnYard {
// Function to check if any two numbers sum up to the target
public static void hasPairWithSum(int[] nums, int n, int target) {
// Outer loop: iterates through each element as the first element of the pair
for (int i = 0; i < n; i++) {
// Inner loop: iterates through each element as the second element of the pair except the first element
for (int j = 0; j < n; j++) {
// If the indexes are the same, skip
if (i == j) continue;
// Check if the sum of nums[i] and nums[j] equals the target
if (nums[i] + nums[j] == target) {
// Print true if such a pair is found and return
System.out.println("true");
return;
}
}
}
// Print false if no such pair is found after checking all pairs
System.out.println("false");
}
}
Python
# Function to check if any two numbers sum up to the target
def has_pair_with_sum(nums, n, target):
# Outer loop: iterates through each element as the first element of the pair
for i in range(n):
# Inner loop: iterates through each element as the second element of the pair except the first element
for j in range(n):
# If the indexes are the same, skip
if i == j:
continue
# Check if the sum of nums[i] and nums[j] equals the target
if nums[i] + nums[j] == target:
# Print true if such a pair is found and return
print("true")
return
# Print false if no such pair is found after checking all pairs
print("false")
Javascript
// Function to check if any two numbers sum up to the target
function hasPairWithSum(nums, n, target) {
// Outer loop: iterates through each element as the first element of the pair
for (let i = 0; i < n; i++) {
// Inner loop: iterates through each element as the second element of the pair except the first element
for (let j = 0; j < n; j++) {
// If the indexes are the same, skip
if (i === j) continue;
// Check if the sum of nums[i] and nums[j] equals the target
if (nums[i] + nums[j] === target) {
// Print true if such a pair is found and return
console.log("true");
return;
}
}
}
// Print false if no such pair is found after checking all pairs
console.log("false");
}
Time Complexity
The code contains two nested loops:
When we have an outer loop running n times and an inner loop also running n times for each iteration of the outer loop, the total number of iterations can be calculated as follows:
- For each iteration of the outer loop, the inner loop runs n times.
- Since the outer loop itself runs n times, the total number of iterations (or operations) performed by the nested loop structure is: n×n = n^2 times
The algorithm performs n² operations, leading to an overall time complexity of O(n²)
Space Complexity
The space complexity considers both the total space used by the algorithm, including the input, and the auxiliary space, which is the extra space used by the algorithm excluding the input.
Total Space Complexity: The total space complexity is O(n) because the input array takes O(n) space, where n is the size of input array.
Auxiliary Space: The auxiliary space complexity is also O(1) since the only extra space used by the algorithm is for storing the loop counters and the result of the comparison, which do not depend on the size of the input array.