Target Sum | Problems in Arrays - 1 | Lecture 14 | C++ and DSA Foundation Course

Key Concepts

• Vectors: Dynamic arrays that can resize automatically.
• Target Sum: Finding pairs or triplets in an array that sum to a specific value.
• Array Manipulation: Modifying array elements to achieve a desired outcome.
• Dry Run: Manually executing code with sample input to trace variable changes.
• Time Complexity: Efficiency of an algorithm in terms of execution time.
• Space Complexity: Efficiency of an algorithm in terms of memory usage.
• Reverse Operation: Reversing the order of elements within a specified range.
• Frequency Array: An array used to store the frequency of elements in another array.
• Pre-processing: Performing initial computations to optimize subsequent operations.

Target Sum Pairs

Problem: Find the number of pairs in an array whose sum equals a given target value (X).

Methodology:

1. Use nested loops. The outer loop iterates through each element of the array.
2. The inner loop iterates through the remaining elements of the array (starting from the next element after the outer loop's current element).
3. For each pair, check if their sum equals the target value.
4. If the sum equals the target value, increment a counter.

Example:

Array: [3, 4, 6, 7, 1]
Target Sum: 7
Pairs: (3, 4), (6, 1)
Answer: 2

Code Snippet:

int arr[] = {3, 4, 6, 7, 1};
int targetSum = 7;
int pairs = 0;
int size = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < size; i++) {
    for (int j = i + 1; j < size; j++) {
        if (arr[i] + arr[j] == targetSum) {
            pairs++;
        }
    }
}

Target Sum Triplets

Problem: Find the number of triplets in an array whose sum equals a given target value (X).

Methodology:

1. Use three nested loops. The outermost loop iterates through each element of the array.
2. The second loop iterates through the remaining elements of the array (starting from the next element after the outermost loop's current element).
3. The innermost loop iterates through the remaining elements of the array (starting from the next element after the second loop's current element).
4. For each triplet, check if their sum equals the target value.
5. If the sum equals the target value, increment a counter.

Example:

Array: [3, 1, 2, 4, 0, 6]
Target Sum: 6
Triplets: (3, 1, 2), (2, 4, 0)
Answer: 2

Code Snippet:

int arr[] = {3, 1, 2, 4, 0, 6};
int targetSum = 6;
int triplets = 0;
int size = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < size; i++) {
    for (int j = i + 1; j < size; j++) {
        for (int k = j + 1; k < size; k++) {
            if (arr[i] + arr[j] + arr[k] == targetSum) {
                triplets++;
            }
        }
    }
}

Finding the Unique Element

Problem: Given an array where all elements are repeated twice except for one unique element, find the unique element.

Methodology:

1. Use nested loops to find pairs of repeating elements.
2. When a pair is found, replace both elements with a specific value (e.g., -1) to mark them as processed.
3. After processing all pairs, iterate through the array and find the element that is not equal to the replacement value. This element is the unique element.

Example:

Array: [2, 3, 2, 4, 1, 3, 1]
Unique Element: 4

Code Snippet:

int arr[] = {2, 3, 2, 4, 1, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < size; i++) {
    for (int j = i + 1; j < size; j++) {
        if (arr[i] == arr[j]) {
            arr[i] = -1;
            arr[j] = -1;
            break;
        }
    }
}

int uniqueElement = 0;
for (int i = 0; i < size; i++) {
    if (arr[i] != -1) {
        uniqueElement = arr[i];
        break;
    }
}

Finding the Second Largest Element

Problem: Find the second largest element in a given array.

Methodology (Initial - Assuming Unique Elements):

1. Find the largest element in the array.
2. Replace the largest element with a minimum value (e.g., -1).
3. Find the largest element again. This will be the second largest element in the original array.

Methodology (Handling Duplicate Elements):

1. Find the largest element in the array.
2. Replace all occurrences of the largest element with a minimum value (e.g., -1).
3. Find the largest element again. This will be the second largest element in the original array.

Optimized Methodology (Single Traversal):

1. Initialize max and secondMax to the minimum possible integer value (INT_MIN).
2. Iterate through the array.
   • If an element is greater than max, update secondMax to the current value of max and update max to the current element.
   • Else if an element is greater than secondMax and not equal to max, update secondMax to the current element.
3. secondMax will hold the second largest element.

Code Snippet (Optimized):

#include <iostream>
#include <climits>

int findSecondLargest(int arr[], int size) {
    int max = INT_MIN;
    int secondMax = INT_MIN;

    for (int i = 0; i < size; i++) {
        if (arr[i] > max) {
            secondMax = max;
            max = arr[i];
        } else if (arr[i] > secondMax && arr[i] != max) {
            secondMax = arr[i];
        }
    }

    return secondMax;
}

Rotating an Array

Problem: Rotate an array by K steps to the right.

Methodology (Using Extra Space):

1. Create a new array of the same size as the original array.
2. Copy the last K elements of the original array to the beginning of the new array.
3. Copy the remaining elements of the original array to the end of the new array.

Methodology (In-Place using Reversal):

1. Reverse the entire array.
2. Reverse the first K elements of the array.
3. Reverse the remaining N-K elements of the array.

Code Snippet (In-Place using Reversal):

#include <iostream>
#include <vector>
#include <algorithm>

void rotateArray(std::vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n; // Handle cases where k > n

    std::reverse(arr.begin(), arr.end());
    std::reverse(arr.begin(), arr.begin() + k);
    std::reverse(arr.begin() + k, arr.end());
}

Querying for Element Presence

Problem: Given an array and a set of queries, determine if each query element is present in the array.

Methodology (Using Frequency Array):

1. Create a frequency array of size equal to the maximum possible value in the array.
2. Iterate through the original array and update the frequency array to store the count of each element.
3. For each query, check the corresponding index in the frequency array. If the value is greater than 0, the element is present; otherwise, it is not.

Code Snippet:

#include <iostream>
#include <vector>

int main() {
    int arr[] = {2, 3, 4, 5, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    int maxElement = 7; // Assuming max element is known

    std::vector<int> frequency(maxElement + 1, 0);

    for (int i = 0; i < size; i++) {
        frequency[arr[i]]++;
    }

    int numQueries = 3;
    int queries[] = {2, 1, 8};

    for (int i = 0; i < numQueries; i++) {
        if (frequency[queries[i]] > 0) {
            std::cout << queries[i] << " is present " << frequency[queries[i]] << " times." << std::endl;
        } else {
            std::cout << queries[i] << " is not present." << std::endl;
        }
    }

    return 0;
}

Synthesis/Conclusion

The lecture covered several array-related problems, emphasizing different approaches to solving them. Key takeaways include:

• Understanding the importance of considering input constraints (e.g., unique vs. duplicate elements).
• Exploring various techniques like array manipulation, frequency arrays, and reversal algorithms.
• Analyzing the trade-offs between different solutions in terms of time complexity, space complexity, and code complexity.
• Recognizing the benefits of using built-in functions like reverse in vectors for efficient code.
• Applying pre-processing techniques to optimize query-based problems.