Array IV
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
10. 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.
To extend the approach we've used for finding two elements that sum up to a target value, we can apply the same logic to find three elements that sum up to a target value.
11. Given an array of integers, we need to check if there exist three distinct elements in the array such that their sum equals a given target value. If such a triplet exists, the function should print true; otherwise, it should print false.
Example
Input: nums = [2, 7, 11, 15, 12, 10], target = 24
Output: true
Explanation: The elements 2, 7, and 15 sum up to 24.
Input: nums = [2, 7, 11, 15], target = 20
Output: false
Explanation: No three elements in the array sum up to 20.
Approach
To solve this problem, we want 3 numbers from the array to check whether their sum satisfies the target.
How can we get those three numbers?
To find the triplet of numbers that satisfies the target condition, we need to check all possible combinations of three different elements in the array. If we find any triplet that meets the condition, we can conclude that such a triplet exists and the answer will be true.
So, let's think about how we can systematically check each triplet of elements in the array. We can imagine iterating through each element in the array and checking it against every other 2 elements to see if their combined sum equals the target.
Detailed Explanation
We can say that we want a triplet that satisfies:
First Element + Second Element + Third 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].
First Element = 2 (at index 0).
Selecting the Second Element:
Next, we look at each of the other elements in the array to find the second element. Since we need three distinct elements, we skip the index of the first element. Here, we skip index 0 where the value 2 is located.
- Skipping Index 0: The first element is at index 0, so we cannot select index 0 as the second element.
- Second Element Options: We can select any element from indices 1, 2, 3, 4, or 5 as the second element.
Selecting the Third Element:
Now, for every possible second element, we will select a third element from the remaining array. We have to consider different elements, so the index of the first element can't be the same as the second or third element, and the index of the second element can't be the same as the third element.
For example:
- At index 0 (first element 2), we skip considering index 0 for the second and third elements.
- At index 1, we select 7 as the second element, so the third element must be from the remaining indices.
We check:
- Add 2 + 7 + 11 → 2 + 7 + 11 = 20 (Not the target).
- Add 2 + 7 + 15 → 2 + 7 + 15 = 24 (This matches our target! We can immediately print true here and stop.)
Since we found a triplet that sums to the target value, we don't need to continue checking other combinations.
If we don’t find a matching triplet with 2 as the first element and 7 as the second element after considering all valid indices for the third element, we continue by changing the second element. Specifically, we move from 7 to the next element in the array and then check again for a valid triplet by considering all valid indices for the third element.
This process is repeated for every possible second element while keeping the first element fixed. Once we’ve exhausted all possibilities for the second element, we then change the first element from 2 to the value at the next index.
We repeat the same process: for each new first element, we iterate through all potential second elements, and for each pair of first and second elements, we consider all possible third elements.
By systematically changing the first and second elements and checking every combination of three elements, we ensure that we consider all possible triplets in the array. If no triplet is found that sums to the target value after all possibilities have been checked, we can confidently conclude that no such triplet exists.
How to considering All Triplets via Code?
The answer to this is by using a nested loop structure (a loop inside a loop inside another loop). The first loop is the outer loop, the second loop is the middle loop, and the third loop is the inner loop.
Outer Loop: This loop selects the first element of the triplet. For every position of this first element, we need to find the other two elements.
Middle 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.
Inner Loop: This loop finds the third element to complete the triplet with the current first and second elements. It skips the indexes that are the same as the outer and middle loops to avoid using the same element twice.
Within the inner loop, we check if the sum of the elements selected by the outer, middle, and inner loops equals the target value.
Dry Run
Input Details
- Array: nums[] = {2, 7, 11, 15, 12, 10}
- Size of the array (n): 6
- Target sum: 24
Outer Loop Iteration (Variable i)
The outer loop starts with i = 0. This loop selects the first number (nums[i]) for forming the triplet.
Outer Loop i = 0
- First number: nums[i] = nums[0] = 2
Middle Loop Iteration (Variable j)
The middle loop starts with j = 0. This loop selects the second number (nums[j]) for forming the triplet.
- Middle Loop j = 0
- nums[j] = nums[0] = 2
- Since i == j, this iteration is skipped.
- Middle Loop j = 1
- nums[j] = nums[1] = 7
Inner Loop Iteration (Variable k)
The inner loop starts with k = 0. This loop selects the third number (nums[k]) for forming the triplet.
- Inner Loop k = 0
- nums[k] = nums[0] = 2
- Since k == i or k == j, this iteration is skipped.
- Inner Loop k = 1
- nums[k] = nums[1] = 7
- Since k == i or k == j, this iteration is skipped.
- Inner Loop k = 2
- nums[k] = nums[2] = 11
- Check: nums[i] + nums[j] + nums[k] = 2 + 7 + 11 = 20
- The sum does not equal the target.
- Inner Loop k = 3
- nums[k] = nums[3] = 15
- Check: nums[i] + nums[j] + nums[k] = 2 + 7 + 15 = 24
- The sum equals the target.
- Output true and return from the function.
Function Ends
Since a triplet (2, 7, 15) that sums up to the target (24) is found, the program exits early without checking further combinations.
Output
The output is: true
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to check if any three numbers sum up to the target
void hasTripletWithSum(int nums[], int n, int target) {
// Outer loop: iterates through each element as the first element of the triplet
for (int i = 0; i < n; ++i) {
// Middle loop: iterates through each element as the second element of the triplet
for (int j = 0; j < n; ++j) {
// Skip if the indexes are the same as the first element
if (i == j) continue;
// Inner loop: iterates through each element as the third element of the triplet
for (int k = 0; k < n; ++k) {
// Skip if the indexes are the same as the first or second element
if (k == i || k == j) continue;
// Check if the sum of nums[i], nums[j], and nums[k] equals the target
if (nums[i] + nums[j] + nums[k] == target) {
// Print true if such a triplet is found and return
cout << "true";
return;
}
}
}
}
// Print false if no such triplet is found after checking all possibilities
cout << "false";
}
Java
import java.util.Scanner;
public class LearnYard {
// Function to check if any three numbers sum up to the target
public static void hasTripletWithSum(int[] nums, int n, int target) {
// Outer loop: iterates through each element as the first element of the triplet
for (int i = 0; i < n; i++) {
// Middle loop: iterates through each element as the second element of the triplet
for (int j = 0; j < n; j++) {
// Skip if the indexes are the same as the first element
if (i == j) continue;
// Inner loop: iterates through each element as the third element of the triplet
for (int k = 0; k < n; k++) {
// Skip if the indexes are the same as the first or second element
if (k == i || k == j) continue;
// Check if the sum of nums[i], nums[j], and nums[k] equals the target
if (nums[i] + nums[j] + nums[k] == target) {
// Print true if such a triplet is found and return
System.out.println("true");
return;
}
}
}
}
// Print false if no such triplet is found after checking all possibilities
System.out.println("false");
}
}
Python
# Function to check if any three numbers sum up to the target
def has_triplet_with_sum(nums, n, target):
# Outer loop: iterates through each element as the first element of the triplet
for i in range(n):
# Middle loop: iterates through each element as the second element of the triplet
for j in range(n):
# Skip if the indexes are the same as the first element
if i == j:
continue
# Inner loop: iterates through each element as the third element of the triplet
for k in range(n):
# Skip if the indexes are the same as the first or second element
if k == i or k == j:
continue
# Check if the sum of nums[i], nums[j], and nums[k] equals the target
if nums[i] + nums[j] + nums[k] == target:
# Print true if such a triplet is found and return
print("true")
return
# Print false if no such triplet is found after checking all possibilities
print("false")
Javascript
// Function to check if any three numbers sum up to the target
function hasTripletWithSum(nums, n, target) {
// Outer loop: iterates through each element as the first element of the triplet
for (let i = 0; i < n; i++) {
// Middle loop: iterates through each element as the second element of the triplet
for (let j = 0; j < n; j++) {
// Skip if the indexes are the same as the first element
if (i === j) continue;
// Inner loop: iterates through each element as the third element of the triplet
for (let k = 0; k < n; k++) {
// Skip if the indexes are the same as the first or second element
if (k === i || k === j) continue;
// Check if the sum of nums[i], nums[j], and nums[k] equals the target
if (nums[i] + nums[j] + nums[k] === target) {
// Print true if such a triplet is found and return
console.log("true");
return;
}
}
}
}
// Print false if no such triplet is found after checking all possibilities
console.log("false");
}
Time Complexity
The time complexity of this solution involves three nested loops.
Each loop runs n times, where n is the size of the input array. Therefore, the total number of iterations (or operations) performed by the three nested loops is n × n × n = n^3.
This leads to an overall time complexity of O(n³).
Space Complexity
Total Space Complexity: The total space complexity is O(n) because the input array takes O(n) space.
Auxiliary Space: The auxiliary space complexity is O(1) since only loop counters and comparison results are stored, which do not depend on the size of the input array.
In various problem-solving scenarios, we often need to identify key characteristics of a dataset, such as determining the most significant value. For instance, finding the maximum element in an array is a fundamental task that helps us locate the highest point of interest, whether it's the largest number, highest score, or maximum profit. Let’s delve into how this can be accomplished.
12. Given an array of integers, we need to find the maximum element in the array. The function should print the maximum value found in the array.
Example
Input: nums = [2, 7, 11, 15, 12, 10]
Output: 15
Explanation: The maximum element in the array is 15.
Input: nums = [3, 4, 1, 5, 2, 5, 1, 10]
Output: 10
Explanation: The maximum element in the array is 10.
Approach
Imagine you're standing in a queue of people, and your goal is to find the tallest person in the line. You start by assuming that the first person you see is the tallest. As you walk down the line, you compare each person with the tallest one you've seen so far. If you find someone taller, you update your "tallest" to that person. By the time you reach the end of the queue, the last person you identified as the tallest is indeed the tallest person in the entire line. This is exactly how the algorithm for finding the maximum element in an array works.
We will use this logic to find the maximum number of a given array too…!
To solve this problem, we need to traverse the entire array(same we walked through the entire queue) and keep track of the maximum element(tallest person) encountered during the traversal. We start by assuming that the first element in the array is the maximum.
Why assume maximum as the first element(nums[0]) in the beginning?
Assuming the first element to be the maximum initially provides a reference point for comparison. As we iterate through the array, we compare each element with this assumed maximum, updating it whenever we find a larger value. This method simplifies finding the maximum by ensuring we always have the largest value encountered so far.
Let's say our array is nums = [2, 7, 11, 15, 12, 10]. Initially, we assume the maximum element is 2 (the first element).
We then iterate through the array, starting from the second element. For each element, we compare it with the current maximum element. If the current element is greater than the current maximum, we update the maximum element to be the current element.
Comparison Process
- First Comparison:
- We compare 7 (the second element) with 2 (the current maximum).
- Since 7 > 2, we update the maximum to 7.
- Second Comparison:
- We then compare 11 (the third element) with 7 (the current maximum).
- Since 11 > 7, we update the maximum to 11.
- Third Comparison:
- Next, we compare 15 (the fourth element) with 11 (the current maximum).
- Since 15 > 11, we update the maximum to 15.
- Fourth Comparison:
- We compare 12 (the fifth element) with 15 (the current maximum).
- Since 12 < 15, we do not update the maximum.
- Fifth Comparison:
- Finally, we compare 10 (the sixth element) with 15 (the current maximum).
- Since 10 < 15, we do not update the maximum.
After completing the traversal of the array, the value of the maximum element will be the largest number in the array. In this case, the maximum value is 15.
Dry Run
Input Details
- Array: nums[] = {2, 7, 11, 15, 12, 10}
- Size of the array (n): 6
Initialization
- The function findMaxElement is called with the input array nums[] and its size n = 6.
- Variable maxElement is initialized to the first element of the array, which is 2.
Iteration Through the Array
First Iteration (i = 1)
- Current element: nums[1] = 7
- Comparison: Is nums[1] > maxElement? (Is 7 > 2?)
- Yes, so maxElement is updated to 7.
Second Iteration (i = 2)
- Current element: nums[2] = 11
- Comparison: Is nums[2] > maxElement? (Is 11 > 7?)
- Yes, so maxElement is updated to 11.
Third Iteration (i = 3)
- Current element: nums[3] = 15
- Comparison: Is nums[3] > maxElement? (Is 15 > 11?)
- Yes, so maxElement is updated to 15.
Fourth Iteration (i = 4)
- Current element: nums[4] = 12
- Comparison: Is nums[4] > maxElement? (Is 12 > 15?)
- No, so maxElement remains 15.
Fifth Iteration (i = 5)
- Current element: nums[5] = 10
- Comparison: Is nums[5] > maxElement? (Is 10 > 15?)
- No, so maxElement remains 15.
Completion
- The loop ends after checking all elements in the array.
- The value of maxElement, which is 15, is printed as the maximum element.
Output
The output is: The maximum element is: 15
Code for All Languages
C++
#include <iostream>
using namespace std;
// Function to find the maximum element in the array
void findMaxElement(int nums[], int n) {
// Initialize the maximum with the first element of the array
int maxElement = nums[0];
// Iterate through the array starting from the second element
for (int i = 1; i < n; ++i) {
// Compare the current element with the maximum element
if (nums[i] > maxElement) {
// Update the maximum element if the current element is larger
maxElement = nums[i];
}
}
// Print the maximum element found in the array
cout << maxElement << endl;
}
Java
import java.util.Scanner;
public class LearnYard {
// Function to find the maximum element in the array
public static void findMaxElement(int[] nums, int n) {
// Initialize the maximum with the first element of the array
int maxElement = nums[0];
// Iterate through the array starting from the second element
for (int i = 1; i < n; i++) {
// Compare the current element with the maximum element
if (nums[i] > maxElement) {
// Update the maximum element if the current element is larger
maxElement = nums[i];
}
}
// Print the maximum element found in the array
System.out.println(maxElement);
}
}
Python
# Function to find the maximum element in the array
def find_max_element(nums, n):
# Initialize the maximum with the first element of the array
max_element = nums[0]
# Iterate through the array starting from the second element
for i in range(1, n):
# Compare the current element with the maximum element
if nums[i] > max_element:
# Update the maximum element if the current element is larger
max_element = nums[i]
# Print the maximum element found in the array
print(max_element)
Javascript
// Function to find the maximum element in the array
function findMaxElement(nums, n) {
// Initialize the maximum with the first element of the array
let maxElement = nums[0];
// Iterate through the array starting from the second element
for (let i = 1; i < n; i++) {
// Compare the current element with the maximum element
if (nums[i] > maxElement) {
// Update the maximum element if the current element is larger
maxElement = nums[i];
}
}
// Print the maximum element found in the array
console.log(maxElement);
}
Time Complexity
The time complexity of this solution is linear, O(n), because we need to traverse all n elements in the array exactly once to determine the maximum.
Space Complexity
The total space complexity is O(n) because the input array takes up O(n) space.
The auxiliary space complexity is O(1) since we only need a single variable to keep track of the maximum element, which does not depend on the size of the array.