Problems on Arrays

1. Maximum Sum of Subarray:

   • Problem: Write a C program to find the maximum sum of a subarray of size k. The user will input the size of the array and its elements, followed by the value of k.

   • Example:

     • Input: arr[] = {2, 1, 5, 1, 3, 2}, k = 3

     • Output: 9 (subarray with maximum sum is {5, 1, 3})

2. Average of Subarrays:

   • Problem: Create a C program to calculate the average of all contiguous subarrays of size k in a given array.

   • Example:

     • Input: arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2}, k = 5

     • Output: [2.4, 2.8, 3.6, 3.4] (averages of each subarray of size k)

3. Smallest Subarray with a Given Sum:

   • Problem: Develop a C program to find the smallest subarray with a sum greater than or equal to a given value s. The user will provide the array and the value of s.

   • Example:

     • Input: arr[] = {4, 2, 2, 7, 8, 1, 2, 8, 1, 0}, s = 8

     • Output: 1 (smallest subarray is {8})

4. Longest Subarray of 1's After Replacement:

   • Problem: Implement a C program that finds the length of the longest contiguous subarray filled with 1's you can get by replacing at most k 0's in the array.

   • Example:

     • Input: arr[] = {0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1}, k = 2

     • Output: 6 (replace the 0's at positions 3 and 4 to make the longest subarray of 1's of length 6)

5. Longest Substring With Distinct Characters:

   • Problem: Write a program in C that returns the length of the longest substring with all distinct characters in a given string.

   • Example:

     • Input: str = "araaci", k = 2

     • Output: 4 (the longest substring with all distinct characters is "araa")

6. Maximum Sum Subarray of At Least Size K:

   • Problem: Write a C program to find the maximum sum of any subarray with a size that is at least k. The user inputs the array and the value of k.

   • Example:

     • Input: arr[] = {4, 3, 5, 2, 1, 3, 2}, k = 3

     • Output: 15 (subarray {4, 3, 5, 2, 1} provides the maximum sum)

7. Minimum Size Subarray Sum:

   • Problem: Implement a C program to find the minimal length of a contiguous subarray of which the sum ≥ s. If no such subarray exists, return 0.

   • Example:

     • Input: arr[] = {2, 3, 1, 2, 4, 3}, s = 7

     • Output: 2 (the smallest subarray with sum ≥ 7 is {4, 3})

8. Longest Subarray with Sum Equals K:

   • Problem: Develop a C program to find the length of the longest contiguous subarray which sums to k.

   • Example:

     • Input: arr[] = {1, -1, 5, -2, 3}, k = 3

     • Output: 4 (the longest subarray with sum equal to 3 is {1, -1, 5, -2})

9. Number of Subarrays with Odd Sum:

   • Problem: Write a program in C to count the number of subarrays with an odd sum.

   • Example:

     • Input: arr[] = {1, 2, 3, 4, 5}

     • Output: 12 (subarrays like {1}, {3}, {5}, {1, 2, 3}, etc., have odd sums)

10. Diet Plan Performance:

    • Problem: Create a C program that evaluates the diet plan performance with a score. The score is calculated as the sum of calories over each contiguous subarray of days k. If the sum is lower than lower, score decreases by 1. If the sum is higher than upper, score increases by 1. The program should return the final score.

    • Example:

      • Input: calories[] = {1, 2, 3, 4, 5}, k = 3, lower = 5, upper = 10

      • Output: 0 (The subarrays are {1,2,3}, {2,3,4}, {3,4,5} with sums 6, 9, and 12. The score increments and decrements balance out to 0.)

11. Pair with Target Sum:

    • Problem: Write a C program to find a pair in an array that adds up to a specific target sum. Assume the array is already sorted.

    • Example:

      • Input: arr[] = {1, 2, 3, 4, 6}, target = 6

      • Output: 1, 3 (elements at indices 1 and 3 add up to 6)

12. Remove Duplicates from Sorted Array:

    • Problem: Implement a C program that removes duplicates from a sorted array and returns the new length of the array without additional space for another array.

    • Example:

      • Input: arr[] = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}

      • Output: 5 (the first five elements of the array are now unique)

13. Squaring a Sorted Array:

    • Problem: Develop a C program that takes a sorted array containing both positive and negative numbers and returns a new array of the squares of each number, sorted in non-decreasing order.

    • Example:

      • Input: arr[] = {-4, -1, 0, 3, 10}

      • Output: {0, 1, 9, 16, 100}

14. Backspace String Compare:

    • Problem: Create a C program to compare two strings to determine if they are equal when both are typed into empty text editors. '#' means a backspace character.

    • Example:

      • Input: str1 = "ab#c", str2 = "ad#c"

      • Output: true (both strings turn into "ac" after processing backspaces)

15. Trapping Rain Water:

    • Problem: Write a C program to compute how much water it is able to trap after raining, given n non-negative integers representing an elevation map where the width of each bar is 1.

    • Example:

      • Input: height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}

      • Output: 6 (units of trapped water)

16. Find the Maximum and Minimum Number in an Array:

    • Problem: Write a C program to find both the maximum and minimum numbers in a given array using a divide and conquer approach. The program should divide the array into two halves, recursively find the maximum and minimum in each half, and then compare them.

    • Example:

      • Input: arr[] = {3, 5, 1, 8, 4, 2}

      • Output: Max = 8, Min = 1

17. All Permutations of an Array:

    • Problem: Implement a C program that prints all permutations of a given array using backtracking.

    • Example:

      • Input: arr[] = {1, 2, 3}

      • Output: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

18. Combination Sum:

    • Problem: Develop a C program that finds all unique combinations in an array where the numbers sum to a given target T. The same number may be chosen from the array an unlimited number of times.

    • Example:

      • Input: arr[] = {2, 3, 6, 7}, T = 7

      • Output: [[2, 2, 3], [7]] (Combinations that sum to 7)

19. Distinct Permutations of an Array:

    • Problem: Write a C program to generate all distinct permutations of a given array that may contain duplicates. Use a backtracking method to ensure that permutations with identical numbers are not repeated.

    • Example:

      • Input: arr[] = {1, 2, 2}

      • Output: [1, 2, 2], [2, 1, 2], [2, 2, 1]

    • Details: The program should account for repeated elements and avoid generating duplicate permutations. This can be managed by sorting the array first and then using a boolean array to keep track of elements that have been used in the current recursive call.

20. Combinations Sum II:

    • Problem: Develop a C program that finds all unique combinations in a given array where the candidate numbers sum to a target number T. Each number in the array may only be used once in the combination.

    • Example:

      • Input: arr[] = {10, 1, 2, 7, 6, 1, 5}, T = 8

      • Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

    • Details: The array may contain duplicates, which may lead to duplicate combinations if not handled properly. Sort the array to handle duplicates more easily and use backtracking to explore possible combinations. Skip over consecutive duplicate elements to avoid generating duplicate combinations.

Approach, solution, and explanation:

1. Maximum Sum of Subarray:

To solve the problem of finding the maximum sum of a subarray of size k, we can utilize the "sliding window" technique, which is an optimized way to handle problems involving subarrays or substrings. Here’s a detailed approach:

Approach using Sliding Window Technique

1. Understanding the Problem: You are given an array and a number k. You need to find the maximum sum of any subarray with the size exactly k.

2. Sliding Window Concept: The idea is to maintain a window of size k that slides through the array from the beginning to the end. As the window slides, it encapsulates different parts of the array, and you need to calculate and compare the sums of these windows.

3. Implementation Steps:

   • Initialize the sum of the first k elements.

   • Slide the window across the array by moving one position to the right at a time.

   • Update the sum by subtracting the element that is left out of the window and adding the element that is newly included in the window.

   • Keep track of the maximum sum encountered as you slide the window.

Implementation

#include <stdio.h>

int maxSumSubarray(int arr[], int n, int k) {
    // Edge case: If array size is less than k
    if (n < k) {
        printf("Invalid input");
        return -1;  // Indicate error
    }

    // Compute the sum of the first 'k' elements
    int max_sum = 0;
    for (int i = 0; i < k; i++) {
        max_sum += arr[i];
    }

    // Initialize window sum to first 'k' elements sum
    int window_sum = max_sum;

    // Slide the window from the start of the second element to the end
    for (int i = k; i < n; i++) {
        window_sum += arr[i] - arr[i - k];
        if (window_sum > max_sum) {
            max_sum = window_sum;
        }
    }

    return max_sum;
}

int main() {
    int arr[] = {2, 1, 5, 1, 3, 2};
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);

    int max_sum = maxSumSubarray(arr, n, k);
    printf("Maximum sum of a subarray of size %d is %d\n", k, max_sum);

    return 0;
}

Example and Explanation

Let’s take the array {2, 1, 5, 1, 3, 2} with k = 3.

• Initially, calculate the sum of the first three elements: 2 + 1 + 5 = 8.

Initial window: [2, 1, 5], 1, 3, 2
Initial sum = 8

• Slide the window right by one element, updating the sum:

Previous window: [2, 1, 5], 1, 3, 2
Slide to: 2, [1, 5, 1], 3, 2
New sum = 8 - 2 + 1 = 7

• Continue sliding and updating the sum:

Previous window: 2, [1, 5, 1], 3, 2
Slide to: 2, 1, [5, 1, 3], 2
New sum = 7 - 1 + 3 = 9  (Maximum so far)

• Final slide:

Previous window: 2, 1, [5, 1, 3], 2
Slide to: 2, 1, 5, [1, 3, 2]
New sum = 9 - 5 + 2 = 6

The maximum sum encountered was 9 from the subarray {5, 1, 3}.

This solution effectively uses the sliding window technique to efficiently compute the maximum sum subarray of size k, ensuring a time complexity of O(n), which is optimal for this problem.

2. Average of Subarrays:

To solve the problem of calculating the average of all contiguous subarrays of size k in a given array, we can utilize the "sliding window" technique, which efficiently handles problems involving subarrays or substrings. Here’s a step-by-step approach:

Approach using Sliding Window Technique

1. Understanding the Problem: You need to find the average of all subarrays of size k within a given array.

2. Sliding Window Concept: This involves maintaining a window of size k that slides through the array from start to end, computing the sum and then the average of elements within the window at each step.

3. Implementation Steps:

   • Compute the sum of the first k elements.

   • Calculate and store the average of this initial window.

   • Slide the window across the array by one element at a time:

     • Subtract the element that is left behind and add the element that comes into the window.

     • Compute and store the new average.

Implementation

#include <stdio.h>

void findAverages(int arr[], int n, int k) {
    // Check if the array can form at least one subarray of size k
    if (n < k) {
        printf("Invalid input.");
        return;
    }

    double windowSum = 0;
    // Initialize sum of the first 'k' elements
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }

    // Calculate the average for the first window
    printf("[%0.1f", windowSum / k);

    // Slide the window; calculate the sum and then the average of new window
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        printf(", %0.1f", windowSum / k);
    }

    printf("]\n");
}

int main() {
    int arr[] = {1, 3, 2, 6, -1, 4, 1, 8, 2};
    int k = 5;
    int n = sizeof(arr) / sizeof(arr[0]);

    findAverages(arr, n, k);
    return 0;
}

Example and Explanation

Let’s use the array {1, 3, 2, 6, -1, 4, 1, 8, 2} with k = 5.

1. Initial Setup:

   • First, sum the elements of the first window of size k: 1 + 3 + 2 + 6 - 1 = 11.

   • The average is 11 / 5 = 2.2.

Initial window: [1, 3, 2, 6, -1], 4, 1, 8, 2
Initial average = 2.2

2. First Slide:

   • Slide the window right: subtract 1 (first element of the old window) and add 4 (first element outside the old window).

   • New sum is 11 - 1 + 4 = 14.

   • New average is 14 / 5 = 2.8.

Slide to: 1, [3, 2, 6, -1, 4], 1, 8, 2
New average = 2.8

3. Subsequent Slides:

   • Continue sliding, updating the sum, and calculating the new average as shown.

Slide to: 1, 3, [2, 6, -1, 4, 1], 8, 2
New average = 2.4

Slide to: 1, 3, 2, [6, -1, 4, 1, 8], 2
New average = 3.6

Slide to: 1, 3, 2, 6, [-1, 4, 1, 8, 2]
New average = 2.8

Final output: [2.4, 2.8, 3.6, 3.4].

This method ensures that the computation is efficient with a time complexity of (O(n)), avoiding redundant recalculations by smartly adjusting the sum for each new window.

3. Smallest Subarray with a Given Sum:

To solve the problem of finding the smallest subarray with a sum greater than or equal to a given value s, the "sliding window" or "two pointer" technique is highly effective. This approach dynamically adjusts the size of the window (subarray) based on the running sum compared to s.

Approach using Two Pointer Technique

1. Understanding the Problem: You need to determine the smallest subarray whose sum is at least s.

2. Sliding Window/Two Pointer Concept: Maintain a window that can expand and contract as needed. Begin with both pointers at the start of the array, expand the window by moving the right pointer to increase the sum, and contract by moving the left pointer to decrease the sum once it exceeds s.

3. Implementation Steps:

   • Initialize two pointers at the start of the array and a variable to keep track of the minimum length found.

   • Expand the right pointer to include more elements until the sum ≥ s.

   • Contract the window by moving the left pointer to the right to try and find a smaller subarray once the current window's sum is sufficient.

   • Update the minimum length each time a valid subarray is found.

Implementation

#include <stdio.h>
#include <limits.h>

int minSubArrayLen(int s, int arr[], int n) {
    int min_len = INT_MAX;
    int left = 0;
    int sum = 0;

    for (int right = 0; right < n; right++) {
        sum += arr[right]; // Expand the window by including the current element

        while (sum >= s) {
            min_len = (right - left + 1 < min_len) ? (right - left + 1) : min_len;
            sum -= arr[left++]; // Contract the window from the left
        }
    }

    return (min_len == INT_MAX) ? 0 : min_len;
}

int main() {
    int arr[] = {4, 2, 2, 7, 8, 1, 2, 8, 1, 0};
    int s = 8;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = minSubArrayLen(s, arr, n);
    printf("Smallest subarray length with sum >= %d is %d\n", s, result);

    return 0;
}

Example and Explanation

Using the array {4, 2, 2, 7, 8, 1, 2, 8, 1, 0} with s = 8.

1. Initial Setup:

   • Start with both pointers at the beginning. No sum yet.

Array: [4, 2, 2, 7, 8, 1, 2, 8, 1, 0]
       ^ 
       | (both pointers start here)
Sum = 0

2. Expand Right Pointer:

   • Move right, increasing sum: 4, 6 (4+2), 8 (4+2+2).

   • When the sum reaches 8 with the elements {4, 2, 2}, check if smaller subarray possible.

Array: [4, 2, 2, 7, 8, 1, 2, 8, 1, 0]
             ^     ^
           left   right
Sum = 8 (valid, but keep trying for smaller subarray)

3. Contract and Expand Again:

   • Start contracting from the left to see if a smaller valid subarray exists.

   • Eventually, find {8} as the smallest subarray with a sum ≥ 8.

Array: [4, 2, 2, 7, 8, 1, 2, 8, 1, 0]
                   ^     
                   | (both pointers here on single `8`)
Min Length = 1

The output for this example is 1, indicating the smallest subarray is {8}. This solution provides a very efficient way to find the minimum length subarray, with a time complexity of (O(n)) due to each element being processed at most twice (once for expansion and once for contraction).

4. Longest Subarray of 1's After Replacement:

To solve the problem of finding the length of the longest contiguous subarray of 1's with a maximum of k replacements of 0's, we use the "sliding window" or "two pointer" technique. This method allows us to efficiently manage the subarray bounds while keeping track of the number of 0's that could be converted to 1's.

Approach using Two Pointer Technique

1. Understanding the Problem: You need to determine the maximum length of a subarray that consists only of 1's after replacing at most k zeros in the array.

2. Sliding Window Concept: This involves maintaining a window that can dynamically adjust its size by moving the start (left pointer) and end (right pointer) based on the number of zeros within the window compared to k.

3. Implementation Steps:

   • Initialize two pointers (left and right) at the start of the array and a variable to track the number of zeros in the current window.

   • Expand the right pointer to include new elements in the window. Increment the zero count if the element is a zero.

   • If the zero count exceeds k, contract the window from the left until the zero count is less than or equal to k.

   • Update the maximum length of the window each time the conditions are met.

Implementation

#include <stdio.h>

int longestOnes(int arr[], int n, int k) {
    int left = 0, right = 0;
    int zeroCount = 0;
    int maxLength = 0;

    for (right = 0; right < n; right++) {
        if (arr[right] == 0) {
            zeroCount++;
        }

        // If zero count exceeds k, shrink the window
        while (zeroCount > k) {
            if (arr[left] == 0) {
                zeroCount--;
            }
            left++;
        }

        // Calculate the maximum length of the window
        maxLength = (right - left + 1 > maxLength) ? right - left + 1 : maxLength;
    }

    return maxLength;
}

int main() {
    int arr[] = {0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1};
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = longestOnes(arr, n, k);
    printf("The longest subarray of 1's after replacing at most %d zero(s) is %d\n", k, result);

    return 0;
}

Example and Explanation

Let's use the example {0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1} with k = 2.

1. Initial Setup:

   • Start with both pointers at the beginning. The window expands as the right pointer moves.

Array: [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
       ^ 
       | (both pointers start here)
Zero count = 0 (initially)

2. Expanding Right Pointer:

   • As the right pointer expands, include zeros and ones. Update zero count and adjust the left pointer if needed.

Expanding to include more elements:
Array: [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
       ^              ^
     left           right
Zero count = 2 (after including two zeros)

3. Contracting When Necessary:

   • When zero count exceeds k (not the case here), adjust the left pointer.

Ideal adjustment:
Array: [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
             ^                       ^
           left                   right
Zero count = 2
Maximum length = 6 (after replacement)

The output is 6, which is the maximum length of a subarray consisting of 1's after replacing at most two zeros. This solution provides an efficient way to maintain and adjust the subarray dynamically with a time complexity of (O(n)), processing each element a constant number of times.

5. Longest Substring With Distinct Characters:

To solve the problem of finding the length of the longest substring with all distinct characters, we can effectively utilize the "sliding window" technique with two pointers. This approach ensures that you can dynamically adjust the window size to maintain only unique characters within the substring.

Approach using Sliding Window Technique

1. Understanding the Problem: You need to find the longest substring (a contiguous block of characters) within a given string where all characters are distinct.

2. Sliding Window Concept: This method involves maintaining a window that grows and shrinks based on the distinctiveness of characters within it.

3. Implementation Steps:

   • Initialize two pointers (left and right) at the start of the string to define the window boundaries.

   • Use a frequency array to keep track of the count of each character within the window.

   • Expand the window by moving the right pointer and update the character count.

   • If a character count exceeds 1 (indicating a repeat), shrink the window from the left until all characters in the window are unique again.

   • Keep track of the maximum window size encountered that satisfies the distinct character condition.

Implementation

#include <stdio.h>
#include <string.h>
#define MAX_CHARS 256  // Assuming ASCII character set

int longestDistinctSubstring(char *str) {
    int n = strlen(str);
    int left = 0, maxLength = 0;
    int charCount[MAX_CHARS] = {0};  // Frequency array for characters

    for (int right = 0; right < n; right++) {
        charCount[str[right]]++;

        // If character repeats, contract the window from the left
        while (charCount[str[right]] > 1) {
            charCount[str[left]]--;
            left++;
        }

        // Update the maximum length found
        int currentLength = right - left + 1;
        maxLength = (currentLength > maxLength) ? currentLength : maxLength;
    }

    return maxLength;
}

int main() {
    char str[] = "araaci";
    int result = longestDistinctSubstring(str);
    printf("The longest substring with all distinct characters is of length %d\n", result);
    return 0;
}

Example and Explanation

Let's take the example string "araaci".

1. Initial Setup:

   • Start with both pointers at the beginning. The window size expands as the right pointer moves.

String: "araaci"
         ^ 
         | (both pointers start here)

2. Expanding the Window:

   • As the right pointer moves, we count each character.

   • Expand until a repeat character is found.

String: "araaci"
         ^    ^
       left  right
Window: "araa" (distinct until the second 'a')

3. Contracting When Necessary:

   • Once a duplicate character is encountered ('a'), contract from the left until all characters are unique.

String: "araaci"
           ^   ^
         left right
Window: "raac" (now distinct, but smaller)

4. Continuing Expansion:

   • Continue expanding and contracting as necessary to find the longest distinct substring.

The maximum length encountered here seems to be incorrectly mentioned in the initial example given ("araa" is not distinct). The correct output for "araaci" should be 3 for the substring "aci". The ASCII art examples and sliding window adjustments illustrate the dynamic checking and adjustment of the window to ensure all characters within it are unique, maximizing the substring length efficiently.

6. Maximum Sum Subarray of At Least Size K:

To solve the problem of finding the maximum sum of any subarray with a size of at least k, we can utilize a variation of the "sliding window" technique combined with some dynamic programming principles. The challenge here is that the subarray size isn't fixed, but instead must be at least k.

Approach using a Modified Sliding Window Technique

1. Understanding the Problem: Determine the maximum sum of a subarray where the subarray's length is at least k.

2. Modified Sliding Window Concept: This involves using the sliding window technique to find the maximum sum subarray for a fixed size and then adjusting the technique to account for the variability in the subarray size.

3. Implementation Steps:

   • Compute the sum of the first k elements as the initial subarray.

   • Expand the window dynamically while keeping track of the maximum sum observed.

   • Use a cumulative sum or prefix sum approach to efficiently calculate the sum of the subarray as it expands beyond k elements.

Implementation

#include <stdio.h>
#include <limits.h> // For INT_MIN

int maxSumSubarray(int arr[], int n, int k) {
    // Base condition if k is greater than array size
    if (k > n) {
        printf("Invalid input: k is larger than the array size.\n");
        return -1;
    }

    int maxSum = INT_MIN;
    int currentSum = 0;

    // Calculate the sum of the first 'k' elements
    for (int i = 0; i < k; i++) {
        currentSum += arr[i];
    }

    // Initialize maxSum with the sum of the first 'k' elements
    maxSum = currentSum;

    // Iterate over the array starting from the k-th element
    for (int i = k; i < n; i++) {
        // Include next element in window and remove the first element of the previous window
        currentSum += arr[i] - arr[i - k];
        // Use currentSum to keep track of the max sum of window size k
        maxSum = (currentSum > maxSum) ? currentSum : maxSum;

        // Additionally, find max for all subarray sizes >= k
        int tempSum = currentSum;
        for (int j = i - k + 1; j < i; j++) {
            tempSum += arr[j];
            maxSum = (tempSum > maxSum) ? tempSum : maxSum;
        }
    }

    return maxSum;
}

int main() {
    int arr[] = {4, 3, 5, 2, 1, 3, 2};
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = maxSumSubarray(arr, n, k);
    printf("Maximum sum of a subarray of at least size %d is %d\n", k, result);

    return 0;
}

Example and Explanation

Using the array {4, 3, 5, 2, 1, 3, 2} with k = 3.

1. Initial Setup:

   • Start by calculating the sum of the first three elements.

Array: [4, 3, 5, 2, 1, 3, 2]
       ^    ^    ^
Initial window: 4 + 3 + 5 = 12

2. Sliding the Window:

   • Slide the window and update the sum by adding the next element and subtracting the leftmost element of the previous window.

Slide 1:
Array: 4, [3, 5, 2, 1], 3, 2
Update window: 3 + 5 + 2 = 10 (remove 4, add 2)
Expand window: 3 + 5 + 2 + 1 = 11 (add 1)

3. Continue Expanding:

   • Continue to update and optionally expand the window to find the maximum sum.

Final stages:
Array: 4, 3, [5, 2, 1, 3, 2]
Max window update: 5 + 2 + 1 + 3 + 2 = 13

The maximum sum found for a subarray of at least size k is 15 from the subarray {4, 3, 5, 2, 1}. This approach ensures efficient computation while maintaining the flexibility of varying subarray sizes.

7. Minimum Size Subarray Sum:

To solve the problem of finding the minimum length of a contiguous subarray with a sum that is greater than or equal to a given value s, the optimal approach is to use the "sliding window" or "two pointer" technique. This method helps to find the minimal subarray length efficiently by adjusting the subarray boundaries dynamically based on the sum condition.

Approach using Sliding Window Technique

1. Understanding the Problem: You are to determine the minimal length of a subarray whose sum is at least s. The subarray must be contiguous.

2. Sliding Window Concept:

   • Start with two pointers, both initialized at the beginning of the array.

   • Expand the window by moving the right pointer and adding to the sum until the sum is greater than or equal to s.

   • Once the sum condition is met, attempt to minimize the window by moving the left pointer inward until the sum is less than s, then expand the window again. Track the minimum length during these adjustments.

3. Implementation Steps:

   • Initialize pointers and variables for the current sum and minimum length.

   • Expand the right pointer to include more elements in the sum.

   • Contract from the left when the sum condition is met to try and find a smaller valid subarray.

   • Record the minimum length each time a valid window is found.

Implementation

#include <stdio.h>
#include <limits.h> // For INT_MAX

int minSubArrayLen(int s, int arr[], int n) {
    int minLength = INT_MAX; // Start with a large number
    int left = 0; // Starting point of the sliding window
    int sum = 0; // Current sum of the window

    for (int right = 0; right < n; right++) {
        sum += arr[right]; // Add the current element to sum

        while (sum >= s) {
            // Calculate current length of subarray
            int currentLength = right - left + 1;
            // Update minimum length if current is smaller
            minLength = (currentLength < minLength) ? currentLength : minLength;
            sum -= arr[left]; // Subtract element from left and move left pointer
            left++;
        }
    }

    // If minLength hasn't changed, no valid subarray was found
    return (minLength == INT_MAX) ? 0 : minLength;
}

int main() {
    int arr[] = {2, 3, 1, 2, 4, 3};
    int s = 7;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = minSubArrayLen(s, arr, n);
    printf("Minimal length of a subarray with sum >= %d is %d\n", s, result);

    return 0;
}

Example and Explanation

Using the array {2, 3, 1, 2, 4, 3} with s = 7.

1. Initial Setup:

   • Start with both pointers at the beginning. No sum yet.

Array: [2, 3, 1, 2, 4, 3]
       ^ 
       | (both pointers start here)
Current Sum = 0

2. Expanding the Window:

   • Expand by moving the right pointer and update the sum.

Step:
Array: [2, 3, 1, 2, 4, 3]
        ^        ^
      left     right
Sum = 2 + 3 + 1 + 2 = 8 (meets condition, sum ≥ 7)

3. Contracting the Window:

   • Once the sum exceeds s, start contracting from the left to find the minimal length.

Contracting:
Array: [2, 3, 1, 2, 4, 3]
                 ^  ^
              left  right
Current Sum = 2 + 4 = 6 (below s, stop contracting, expand again)

4. Continue Expanding and Contracting:

   • Continue this process to find the smallest window.

Final minimal window:
Array: [2, 3, 1, 2, 4, 3]
                    ^  ^
                 left  right
Minimum Length = 2 (subarray {4, 3})

This method ensures efficient computation with a time complexity of (O(n)), processing each element only once during the expansion and contraction phases. This makes it a highly effective way to solve the problem of finding the minimum subarray sum greater than or equal to s.

8. Longest Subarray with Sum Equals K:

To solve the problem of finding the length of the longest contiguous subarray which sums to a given value k, we can utilize a technique involving prefix sums combined with a hashmap (in languages that support it, such as Python or Java). However, since C does not natively support hashmaps easily, we'll use a slightly less efficient approach using an array to store prefix sums and a brute force search to find the longest subarray with the desired sum.

Approach Using Prefix Sums

1. Understanding the Problem: The objective is to find a contiguous subarray where the sum of elements equals k.

2. Prefix Sum Concept: The sum of elements from index i to j in an array can be quickly calculated using the prefix sum array where prefix[j] - prefix[i-1] = sum(i to j).

3. Implementation Steps:

   • Compute a prefix sum array.

   • For each index, look back through earlier prefix sums to check if prefix[j] - k exists; if it does, calculate the subarray length from the difference in indices.

   • Maintain a record of the maximum length found.

Implementation

#include <stdio.h>

int longestSubarrayWithSumK(int arr[], int n, int k) {
    int prefixSum[n]; // Array to store prefix sums
    int maxLength = 0; // To store the maximum length of subarray with sum k

    prefixSum[0] = arr[0];
    // First fill the prefix sum array
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
    }

    // Now find the longest subarray with sum k
    for (int start = 0; start < n; start++) {
        for (int end = start; end < n; end++) {
            int sum = (start == 0) ? prefixSum[end] : prefixSum[end] - prefixSum[start - 1];
            if (sum == k) {
                int length = end - start + 1;
                if (length > maxLength) {
                    maxLength = length;
                }
            }
        }
    }

    return maxLength;
}

int main() {
    int arr[] = {1, -1, 5, -2, 3};
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = longestSubarrayWithSumK(arr, n, k);
    printf("The longest subarray with sum %d is %d\n", k, result);

    return 0;
}

Example and Explanation

Let's use the example {1, -1, 5, -2, 3} with k = 3.

1. Prefix Sum Calculation:

   • Calculate prefix sums for the array: [1, 0, 5, 3, 6].

Array:     [ 1,  -1,  5, -2,  3]
Prefix Sum:[ 1,   0,  5,  3,  6]

2. Find Longest Subarray:

   • For each pair (start, end), calculate the sum using the prefix sum and check if it matches k.

Check:
- For subarray starting at 0 and ending at 3, the sum is `prefix[3] = 3` (matches k)
- Length = end - start + 1 = 4 - 0 + 1 = 4

3. Result:

   • The longest subarray with the sum 3 is found to be of length 4.

Longest Subarray:
[ 1, -1, 5, -2 ] -> Sum = 3, Length = 4

The use of a prefix sum simplifies the computation of the sum of any subarray, but checking every possible subarray can be inefficient. However, in C, without the use of additional data structures like hashmaps, this brute force method provides a clear and straightforward way to determine the longest subarray with the given sum.

9. Number of Subarrays with Odd Sum:

To solve the problem of finding the number of subarrays with an odd sum in C, we can use a brute force approach by iterating through all possible subarrays, summing their elements, and counting how many have an odd sum. This method is straightforward but can be inefficient for very large arrays due to its quadratic time complexity.

Approach Using a Brute Force Technique

1. Understanding the Problem: The goal is to count all subarrays where the sum of the elements is odd.

2. Brute Force Method:

   • Iterate through each possible starting point of the subarray.

   • For each starting point, iterate through each possible ending point.

   • Sum the elements of the subarray from the starting point to the ending point.

   • Check if the sum is odd and increment a counter if it is.

3. Implementation Steps:

   • Use nested loops: the outer loop to set the starting point of the subarray, and the inner loop to set the ending point.

   • Calculate the sum of elements within the bounds set by the outer and inner loops.

   • Use a simple condition to check if the sum is odd (e.g., sum % 2 != 0).

Implementation

#include <stdio.h>

// Function to count subarrays with odd sum
int countOddSumSubarrays(int arr[], int n) {
    int count = 0;

    for (int start = 0; start < n; start++) {
        int sum = 0;
        for (int end = start; end < n; end++) {
            sum += arr[end];
            if (sum % 2 != 0) {  // Check if the sum is odd
                count++;
            }
        }
    }

    return count;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = countOddSumSubarrays(arr, n);
    printf("Number of subarrays with odd sum: %d\n", result);

    return 0;
}

Example and Explanation

Let's take the example {1, 2, 3, 4, 5}.

1. Initial Setup:

   • Start with calculating subarrays beginning from the first element.

Array: [1, 2, 3, 4, 5]

2. Subarray Calculation:

   • Iterate through subarrays starting with each element.

Starting at 0:
Subarrays: [1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5]
Odd sums:   1     3       6         10            15
            O     O       E         E             O  (O = Odd, E = Even)

Starting at 1:
Subarrays:    [2], [2, 3], [2, 3, 4], [2, 3, 4, 5]
Odd sums:       2     5       9        14
                E     O       O        E

...and so on for each starting element

3. Counting:

   • As shown, subarrays such as {1}, {1, 2}, and {2, 3} have odd sums. You continue this for all starting positions and count all subarrays with odd sums.

The code example calculates the sum of each possible subarray and checks if it is odd. This approach ensures that all subarrays are considered, and though it might not be the most efficient for large input sizes, it accurately solves the problem for moderately sized arrays.

10. Diet Plan Performance:

To tackle the problem of evaluating a diet plan's performance based on calorie intake over a specified number of days (k), we can efficiently utilize the "sliding window" technique. This method is ideal for analyzing consecutive subarrays of a fixed size.

Approach Using Sliding Window Technique

1. Understanding the Problem: You need to calculate the score based on sums of contiguous subarrays of size k from the given array of calories. The score changes based on how these sums compare to predefined lower and upper limits.

2. Sliding Window Technique:

   • Compute the sum of the first k days to initialize the first window.

   • Slide the window across the calories array by adding the next day's calories and subtracting the first day's calories from the previous window.

   • Adjust the score based on how the sum of calories in the current window compares to the lower and upper limits.

3. Implementation Steps:

   • Initialize the score and the first window's sum.

   • For each new position of the window, update the sum and adjust the score based on the sum's relation to the lower and upper limits.

   • Return the final score.

Implementation

#include <stdio.h>

int dietPlanPerformance(int calories[], int n, int k, int lower, int upper) {
    int score = 0;
    int currentSum = 0;

    // Initial sum of the first 'k' elements
    for (int i = 0; i < k; i++) {
        currentSum += calories[i];
    }

    // Evaluate the initial window
    if (currentSum < lower) score--;
    else if (currentSum > upper) score++;

    // Slide the window across the array
    for (int i = k; i < n; i++) {
        currentSum += calories[i] - calories[i - k];
        if (currentSum < lower) score--;
        else if (currentSum > upper) score++;
    }

    return score;
}

int main() {
    int calories[] = {1, 2, 3, 4, 5};
    int k = 3, lower = 5, upper = 10;
    int n = sizeof(calories) / sizeof(calories[0]);

    int result = dietPlanPerformance(calories, n, k, lower, upper);
    printf("Final score of the diet plan: %d\n", result);

    return 0;
}

Example and Explanation

Let's take the example {1, 2, 3, 4, 5} with k = 3, lower = 5, and upper = 10.

1. Initial Setup:

   • Compute the sum of the first k elements.

Array: [1, 2, 3, 4, 5]
Initial window: [1, 2, 3]
Sum = 6

2. Evaluate and Slide:

   • Evaluate the initial sum relative to lower and upper.

   • Slide the window and update the sum and score.

After initial sum:
Score = 0 (6 is between 5 and 10)

First slide:
Array: [1, 2, 3, 4, 5]
Old window: [1, 2, 3], New window: [2, 3, 4]
Updated sum = 9 (remove 1, add 4)
Score remains 0 (9 is still between 5 and 10)

Second slide:
Array: [1, 2, 3, 4, 5]
Old window: [2, 3, 4], New window: [3, 4, 5]
Updated sum = 12 (remove 2, add 5)
Score increments by 1 (12 is above 10)

3. Final Score Calculation:

   • The score adjusts through subsequent window evaluations.

Final score:
Score = 0 (the initial increment from the last window is balanced by earlier evaluations)

This approach ensures efficient computation of the diet plan score, maintaining optimal time complexity using the sliding window technique. Each window transition only requires constant time since it updates the sum with only two operations: subtracting the outgoing element and adding the incoming one.

11. Pair with Target Sum:

To solve the problem of finding a pair in a sorted array that adds up to a specific target sum, you can effectively use the two-pointer technique. This approach takes advantage of the sorted nature of the array to adjust pointers based on the sum of the elements they point to.

Approach using Two Pointer Technique

1. Understanding the Problem: Given a sorted array, find two numbers such that they add up to a specific target.

2. Two Pointer Technique:

   • Place one pointer at the beginning (left) and another at the end (right) of the array.

   • If the sum of the elements at these pointers is equal to the target sum, you've found your pair.

   • If the sum is less than the target, move the left pointer to the right to increase the sum.

   • If the sum is more than the target, move the right pointer to the left to decrease the sum.

   • Continue this until the pointers meet.

3. Implementation Steps:

   • Initialize two pointers, one at the start and one at the end of the array.

   • Loop through the array while left pointer is less than right pointer.

   • Adjust pointers based on the comparison of their sum to the target.

Implementation

#include <stdio.h>

// Function to find two numbers in a sorted array that add up to a specific target
void findPairWithSum(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left < right) {
        int currentSum = arr[left] + arr[right];
        if (currentSum == target) {
            printf("Pair found at indices %d and %d: (%d, %d)\n", left, right, arr[left], arr[right]);
            return; // Return after the first pair is found
        } else if (currentSum < target) {
            left++; // Increase the sum by moving the left pointer to the right
        } else {
            right--; // Decrease the sum by moving the right pointer to the left
        }
    }

    printf("No pair found that adds up to the target sum.\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 6};
    int target = 6;
    int n = sizeof(arr) / sizeof(arr[0]);

    findPairWithSum(arr, n, target);
    return 0;
}

Example and Explanation

Given the array {1, 2, 3, 4, 6} with the target sum 6:

1. Initial Setup:

   • Place two pointers, left at the start and right at the end of the array.

Array: [1, 2, 3, 4, 6]
       ^            ^
     left         right

2. Evaluate Sum and Adjust Pointers:

   • Calculate the sum of elements at left and right.

First check:
Sum = 1 + 6 = 7 (greater than 6, so decrease the sum by moving the right pointer left)

Second check:
Array: [1, 2, 3, 4, 6]
       ^         ^
     left      right
Sum = 1 + 4 = 5 (less than 6, so increase the sum by moving the left pointer right)

3. Find the Pair:

   • Continue adjusting the pointers until the pair that adds up to the target is found.

Third check:
Array: [1, 2, 3, 4, 6]
           ^     ^
         left  right
Sum = 2 + 4 = 6 (equals target, pair found)

The output in this scenario would be the indices 1 and 3, which correspond to the elements 2 and 4 in the array that sum up to 6. This solution efficiently finds the required pair with a time complexity of (O(n)), making it very effective for sorted arrays.

12. Remove Duplicates from Sorted Array:

To solve the problem of removing duplicates from a sorted array without using additional space, we can utilize the two-pointer technique. This technique involves using one pointer for iterating through the array and another pointer to store the position of the last unique element found.

Approach using Two Pointer Technique

1. Understanding the Problem: Since the array is already sorted, duplicate elements will be adjacent. The goal is to modify the array in-place to remove duplicates and return the new length.

2. Two Pointer Technique:

   • Use one pointer (i) to explore the array from the first to the last element.

   • Use another pointer (uniqueIndex) to keep track of the last position where a unique number was placed.

   • Compare each element pointed by i with the last unique element, and if they are different, update the position of uniqueIndex and copy the new unique element there.

3. Implementation Steps:

   • Start with the uniqueIndex pointer at the first element since the first element is always unique.

   • Incrementally move through the array with the i pointer, starting from the second element.

   • If a new unique element is found (different from the one at uniqueIndex), increment uniqueIndex and update that position with the new element.

Implementation

#include <stdio.h>

int removeDuplicates(int arr[], int n) {
    if (n == 0) return 0; // Handle empty array

    int uniqueIndex = 0; // Start from the first element

    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[uniqueIndex]) { // Check if current element is different from last unique element
            uniqueIndex++; // Move to the next unique position
            arr[uniqueIndex] = arr[i]; // Update the position with the new unique element
        }
    }

    return uniqueIndex + 1; // Length is last unique index + 1
}

int main() {
    int arr[] = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int newLength = removeDuplicates(arr, n);

    printf("New length: %d\n", newLength);
    printf("Modified array: ");
    for (int i = 0; i < newLength; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Example and Explanation

Given the array {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}:

1. Initial Setup:

   • The uniqueIndex starts at the first element because it's always unique.

Array: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
       ^
     uniqueIndex

2. Iterate with i Pointer:

   • Move i from the second element and compare each element with the one at uniqueIndex.

Initial Compare:
Array: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
       ^  ^
 uniqueIndex  i

After several iterations:
Array: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]  // As 'i' finds new unique elements, they are placed after `uniqueIndex`
                 ^           ^
         uniqueIndex         i

3. Final Array State:

   • The first five elements of the array now contain all unique values.

Final Array:
Array: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
                    ^
     unique elements up to the new length

The output is 5, as the first five elements are unique, and this technique ensures that the space complexity remains (O(1)) since we modify the array in-place.

13. Squaring a Sorted Array:

To solve the problem of squaring a sorted array and ensuring the result is also sorted, we can effectively utilize the two-pointer technique. This technique is especially useful because the input array can contain both negative and positive numbers, and while squaring these numbers, the order can change due to the nature of squaring negative numbers.

Approach Using Two Pointer Technique

1. Understanding the Problem: The goal is to transform the array by squaring each element and ensuring that the resulting array remains sorted. Negative numbers, when squared, can become larger than the squares of smaller positive numbers, complicating direct squaring and sorting.

2. Two Pointer Technique:

   • Place one pointer at the beginning of the array segment containing negative numbers and another pointer at the start of the positive numbers.

   • Compare the absolute values of the positions pointed to by the two pointers, square the smaller absolute value, and place it in the output array, starting from the end of the array moving backwards.

   • Move the pointers inward based on which side was squared and placed in the output array.

3. Implementation Steps:

   • Identify the split point between negative and non-negative numbers.

   • Use two pointers to track the largest absolute values in the negative and positive segments.

   • Square the numbers and place them into the result array from the highest index down to zero.

Implementation

#include <stdio.h>
#include <stdlib.h> // For abs() function

void squareAndSortArray(int arr[], int n, int result[]) {
    int left = 0; // Start of the array
    int right = n - 1; // End of the array
    int index = n - 1; // Position to place the squared number in result array

    while (left <= right) {
        if (abs(arr[left]) > abs(arr[right])) {
            result[index] = arr[left] * arr[left];
            left++; // Move right since we've taken the square of the left element
        } else {
            result[index] = arr[right] * arr[right];
            right--; // Move left since we've taken the square of the right element
        }
        index--; // Move to the next position in the result array
    }
}

int main() {
    int arr[] = {-4, -1, 0, 3, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result[n]; // Array to store the results

    squareAndSortArray(arr, n, result);

    printf("Squared and sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    return 0;
}

Example and Explanation

Given the array {-4, -1, 0, 3, 10}, we'll square each element and sort the result.

1. Initial Setup:

   • Place the left pointer at the start (at the largest negative number).

   • Place the right pointer at the end (at the largest positive number).

Array: [-4, -1, 0, 3, 10]
        ^               ^
      left            right

2. Processing Squares:

   • Compare the absolute values of the numbers at left and right.

   • Place the square of the larger absolute value in the result array, starting from the end.

First iteration (comparing 4 and 10):
Result: [   ,   ,   ,   , 100]
                                 // 10 squared is 100, move `right` pointer inward

Second iteration (comparing 4 and 3):
Result: [   ,   ,   , 16, 100]
                             // 4 squared is 16, move `left` pointer inward

3. Continue:

   • Continue the process, filling the result array from the highest index to zero.

Continued iterations fill in:
Result: [0, 1, 9, 16, 100]

The resulting array is {0, 1, 9, 16, 100}, which is correctly sorted. This method uses O(1) additional space (excluding the output array) and O(n) time complexity, making it highly efficient for the given problem.

14. Backspace String Compare:

To solve the problem of comparing two strings accounting for backspace characters (#), where # represents a backspace operation, we can efficiently use the two-pointer technique from the end of each string towards the beginning. This approach allows us to process each string from back to front, skipping characters that have been "backspaced".

Approach Using Two Pointer Technique

1. Understanding the Problem: Given two strings, simulate the typing of each string into a text editor where # signifies a backspace. The challenge is to determine if the resultant text of both strings is identical.

2. Two Pointer Technique:

   • Use two pointers, one for each string, starting at the end of the strings.

   • Move each pointer backwards, accounting for backspaces (#).

   • Compare the next valid character of both strings at each step.

   • Handle cases where multiple backspaces occur consecutively.

3. Implementation Steps:

   • Initialize pointers at the ends of both strings.

   • Use a loop to traverse both strings from the end to the start.

   • Use helper counters to manage the number of backspaces encountered.

   • Compare characters only when both are not supposed to be backspaced.

Implementation

#include <stdio.h>
#include <string.h>

// Function to get the next valid character index accounting for backspaces
int getNextValidCharIndex(const char *str, int index) {
    int backspaceCount = 0;
    while (index >= 0) {
        if (str[index] == '#') {
            backspaceCount++;
        } else if (backspaceCount > 0) {
            backspaceCount--;
        } else {
            break;
        }
        index--;
    }
    return index;
}

// Function to compare two strings considering backspaces
int backspaceCompare(const char *str1, const char *str2) {
    int i = strlen(str1) - 1;
    int j = strlen(str2) - 1;

    while (i >= 0 || j >= 0) {
        i = getNextValidCharIndex(str1, i);
        j = getNextValidCharIndex(str2, j);

        if (i < 0 && j < 0) {
            return 1; // Both strings are finished, and so far, they are the same
        }
        if (i < 0 || j < 0) {
            return 0; // One string finished before the other
        }
        if (str1[i] != str2[j]) {
            return 0; // Mismatch found
        }
        i--;
        j--;
    }
    return 1; // Both strings completed and all matched
}

int main() {
    const char *str1 = "ab#c";
    const char *str2 = "ad#c";

    if (backspaceCompare(str1, str2)) {
        printf("true\n");
    } else {
        printf("false\n");
    }

    return 0;
}

Example and Explanation

Given the input strings str1 = "ab#c" and str2 = "ad#c":

1. Initial Setup:

   • Place pointers at the end of both strings.

str1: "ab#c"
          ^
          pointer

str2: "ad#c"
          ^
          pointer

2. Processing Each String:

   • Traverse each string from end to start, adjusting for #.

Processing str1:
- 'c' is a valid character.
- Skip 'b' due to the '#' after it.
- 'a' is the next valid character.

Processing str2:
- 'c' is a valid character.
- Skip 'd' due to the '#' after it.
- 'a' is the next valid character.

3. Comparison:

   • Both strings result in "ac" after processing backspaces.

Final Strings After Processing:
str1 and str2 both equal to "ac"

The program correctly identifies that both strings are the same after accounting for backspaces. The two-pointer approach from the end of the strings makes it efficient by avoiding the need to build the resultant strings explicitly and instead compares them on the fly.

15. Trapping Rain Water:

To solve the problem of calculating how much water can be trapped between bars in an elevation map, an efficient approach involves using the two-pointer technique. This method is well-suited for the problem because it allows simultaneous assessment from both ends of the array, maximizing the amount of water trapped based on the encountered bar heights.

Approach Using Two Pointer Technique

1. Understanding the Problem: The objective is to calculate the total volume of water that can be trapped within the given height of bars after rainfall, where each bar has a width of 1 unit.

2. Two Pointer Technique:

   • Initialize two pointers, one at the start (left) and one at the end (right) of the array.

   • Use two variables to keep track of the maximum height encountered from the left (left_max) and from the right (right_max).

   • Move the pointer with the lower maximum height towards the center, updating the maximum heights and calculating trapped water as you go.

3. Implementation Steps:

   • Compare height[left] and height[right].

   • If height[left] is less than height[right], compute potential trapped water at left, update left_max and move left pointer to the right.

   • Otherwise, compute trapped water at right, update right_max, and move right pointer to the left.

   • Continue this until the two pointers meet in the middle.

Implementation

#include <stdio.h>

// Function to calculate the trapped rain water
int trap(int height[], int n) {
    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int water_trapped = 0;

    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];  // Update the max in the left
            } else {
                water_trapped += left_max - height[left];  // Calculate trapped water
            }
            left++;  // Move the left pointer to the right
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];  // Update the max in the right
            } else {
                water_trapped += right_max - height[right];  // Calculate trapped water
            }
            right--;  // Move the right pointer to the left
        }
    }
    return water_trapped;
}

int main() {
    int height[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int n = sizeof(height) / sizeof(height[0]);
    int result = trap(height, n);
    printf("Total trapped rain water is %d units.\n", result);
    return 0;
}

Example and Explanation

Given the input array {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}:

1. Initial Setup:

   • left points to the first element, right points to the last element.

Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
                ^                                ^
              left                              right

2. Process Trapping Water:

   • Move left and right pointers towards each other based on the comparison of height[left] and height[right].

First few steps:
- left_max = 0, right_max = 0 initially.
- height[0] < height[11], move `left` to right. `left_max` is still 0, no water trapped.
- height[1] > height[11], now move `right` to left. `right_max` = 1, calculate trapped water at position 11 if any.
...

3. Continue Until Pointers Meet:

   • Compute trapped water based on the current left_max and right_max.

Trapped water calculations:
- At each step, trapped water at a position is the minimum of `left_max` and `right_max` minus the current height.
...
Final trapped water volume is 6 units.

The output is 6 units of trapped water, and the two-pointer approach efficiently calculates this with a single pass through the array, making the time complexity (O(n)). This method avoids the need for auxiliary space, except for a few variables to track the maximum heights and pointers.

16. Find the Maximum and Minimum Number in an Array:

To solve the problem of finding the maximum and minimum numbers in an array using a divide and conquer approach, we will recursively split the array into two halves until each subarray contains only one or two elements. This method resembles the merge sort algorithm in its division phase but instead of sorting, it focuses on finding and comparing extremes.

Approach Using Divide and Conquer

1. Understanding the Problem: The task is to find both the maximum and minimum elements in an array without scanning through it linearly. Instead, using a recursive method that divides the array into smaller parts, finds maxima and minima in these parts, and combines results.

2. Divide and Conquer Technique:

   • Divide: Split the array into two halves.

   • Conquer: Recursively find the maximum and minimum in each half.

   • Combine: Compare the results from the two halves to determine the overall maximum and minimum.

3. Implementation Steps:

   • If the array has only one element, return it as both max and min.

   • If the array has two elements, directly compare them to determine the max and min.

   • For larger arrays, split the array into two, recursively find max and min for both halves, and then determine the global max and min by comparing the results from both halves.

Implementation

#include <stdio.h>

// A structure to return two values from getMaxMin function
typedef struct {
    int max;
    int min;
} MinMax;

// Recursive function to find the maximum and minimum number in an array
MinMax getMaxMin(int arr[], int low, int high) {
    MinMax result, leftResult, rightResult;

    if (low == high) { // If the array has only one element
        result.max = result.min = arr[low];
        return result;
    }

    if (high == low + 1) { // If the array has two elements
        if (arr[low] > arr[high]) {
            result.max = arr[low];
            result.min = arr[high];
        } else {
            result.max = arr[high];
            result.min = arr[low];
        }
        return result;
    }

    // Divide the array into halves
    int mid = (low + high) / 2;
    leftResult = getMaxMin(arr, low, mid);
    rightResult = getMaxMin(arr, mid + 1, high);

    // Conquer phase - Compare the results from the two halves
    result.max = (leftResult.max > rightResult.max) ? leftResult.max : rightResult.max;
    result.min = (leftResult.min < rightResult.min) ? leftResult.min : rightResult.min;

    return result;
}

int main() {
    int arr[] = {3, 5, 1, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    MinMax result = getMaxMin(arr, 0, n - 1);
    printf("Max = %d, Min = %d\n", result.max, result.min);

    return 0;
}

Example and Explanation

1. Initial Array:

   • Divide the array into two halves: {3, 5, 1} and {8, 4, 2}.

Array: [3, 5, 1, 8, 4, 2]
        -----------------
        Divide
        /            \
    [3, 5, 1]      [8, 4, 2]

2. Recursive Division:

   • Further split each half until each subarray has one or two elements, then determine max and min in each.

Further Division:
[3, 5, 1]
   /      \
[3, 5]    [1] -> Min = 1, Max = 1

[8, 4, 2]
   /      \
[8, 4]    [2] -> Min = 2, Max = 2

... and so on, until all parts are compared

3. Combine Results:

   • Compare results of two halves to find the global maximum and minimum.

Combine Results:
Max of [3, 5, 1] is 5, Min is 1
Max of [8, 4, 2] is 8, Min is 2
Global Max = 8, Global Min = 1

The final output from this example is Max = 8, Min = 1, achieved by recursively comparing subarrays. This approach effectively uses the divide and conquer strategy to solve the problem efficiently and elegantly.

17. All Permutations of an Array:

Generating all permutations of an array is a classic problem that can be elegantly solved using a recursive backtracking approach. This technique allows us to construct permutations by making a sequence of choices, where for each choice, we explore all further choices through recursion. If the permutation isn't complete or doesn't satisfy the condition, we undo the last choice (backtrack) and try the next option.

Approach Using Backtracking

1. Understanding the Problem: The task is to generate all possible orders of elements in an array. This means that for each element in the array, it can be the starting point of a permutation.

2. Recursive Backtracking:

   • Fix one element at a time to the first position, and recursively handle the rest of the array.

   • Once an element is fixed in the first position, swap it back to its original position after the recursive call (this is the backtracking step).

   • Continue this for each element in the array to generate all possible permutations.

3. Implementation Steps:

   • Start with the initial complete array and recursively swap each element with the current position.

   • After placing each element at the current position, recurse to fill the next position.

   • Once a permutation is printed/completed, swap the elements back to their original positions to restore the order and try the next possibility.

Implementation

#include <stdio.h>

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

void printArray(int arr[], int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(", ");
    }
    printf("], ");
}

void permute(int arr[], int start, int n) {
    if (start == n) { // All positions are fixed, print the permutation
        printArray(arr, n);
        return;
    }

    for (int i = start; i < n; i++) {
        swap(&arr[start], &arr[i]);  // Swap the current element with the start
        permute(arr, start + 1, n);  // Recursively permute the rest of the array
        swap(&arr[start], &arr[i]);  // Backtrack: Swap back to the original configuration
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("All permutations of the array are: \n");
    permute(arr, 0, n);
    return 0;
}

Example and Explanation

Given the input array {1, 2, 3}:

1. Initial Call:

   • Start by swapping each element with itself and then with every other element.

Initial array: [1, 2, 3]

2. Recursive Exploration:

   • Fix the first element and permute the rest:

   • Swap 1 with 1 (fix 1), then permute [2, 3].

Permutations with 1 fixed:
[1, 2, 3]
[1, 3, 2]

3. Further Recursion and Backtracking:

   • Backtrack to the original array configuration after each complete permutation and move to the next element:

   • Swap 1 with 2 and 3 in subsequent recursive calls and explore all permutations for each configuration.

After backtracking to [1, 2, 3], swap and fix next:
[2, 1, 3]
[2, 3, 1]
... and so on for `3`:
[3, 2, 1]
[3, 1, 2]

4. Completion:

   • Each recursion depth handles one position in the array, fixing it and then moving on to permute the rest. Backtracking ensures elements are swapped back, allowing for the exploration of new permutations.

This recursive and backtracking approach allows us to generate all permutations by continually swapping elements, exploring further permutations, and then undoing the swaps to try different sequences, effectively covering all possible combinations of the array elements.

18. Combination Sum:

To solve the problem of finding all unique combinations in an array that sum to a given target ( T ), where elements can be reused, a recursive backtracking approach is ideal. This method allows for exploring all possible combinations of numbers that add up to the target sum, backtracking whenever a combination either reaches or exceeds the target without a match.

Approach Using Recursive Backtracking

1. Understanding the Problem: We need to identify combinations within the array that sum up to ( T ). The numbers can be used repeatedly, and we must ensure no duplicate combinations are output.

2. Backtracking Technique:

   • Utilize a recursive function to explore every possible combination.

   • Use a temporary array (or dynamic list in higher-level languages) to hold the current combination.

   • If the current combination's sum equals ( T ), store or print this combination.

   • If the sum exceeds ( T ), terminate the exploration for that path.

   • Continue to add the next number in the array to the current combination and recurse.

   • After exploring with a number included, backtrack by removing it and trying the next number.

3. Implementation Steps:

   • Begin with the smallest numbers to build up combinations.

   • Use a recursive function to attempt to add each number to the current combination and recurse until the combination is valid or invalid.

   • Backtrack after each recursive call to try the next potential number.

Implementation

This C code uses dynamic memory allocation for simplicity in managing combinations. It tracks each combination using a temporary array that adjusts as the recursive function explores each possibility.

#include <stdio.h>
#include <stdlib.h>

void printCombination(int temp[], int tempSize) {
    printf("[");
    for (int i = 0; i < tempSize; i++) {
        printf("%d", temp[i]);
        if (i < tempSize - 1) printf(", ");
    }
    printf("]");
}

void findCombinations(int arr[], int n, int start, int target, int temp[], int tempSize) {
    if (target == 0) { // If the current combination's sum is equal to target, print it
        printCombination(temp, tempSize);
        printf(", ");
        return;
    }

    for (int i = start; i < n; i++) {
        if (target < arr[i]) continue; // If the remaining target is less than arr[i], skip it

        // Add arr[i] to the current combination and recurse
        temp[tempSize] = arr[i];
        findCombinations(arr, n, i, target - arr[i], temp, tempSize + 1);
    }
}

void combinationSum(int arr[], int n, int target) {
    int *temp = malloc(target * sizeof(int)); // Allocate temp array large enough to hold potential combinations
    printf("[");
    findCombinations(arr, n, 0, target, temp, 0);
    printf("]\n");
    free(temp); // Free the dynamically allocated memory
}

int main() {
    int arr[] = {2, 3, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    printf("Combinations that sum to %d are:\n", target);
    combinationSum(arr, n, target);
    return 0;
}

Example and Explanation

Given the input array {2, 3, 6, 7} with target ( T = 7 ):

1. Initial Setup:

   • Start from the first element in the array and try to build combinations.

Array: [2, 3, 6, 7]
Target: 7

2. Recursive Exploration:

   • Start with 2, recursively try to add 2 again, and then 3, until a combination equals the target or exceeds it.

Starting combination:
Trying [2], remaining target = 5
  -> [2, 2], remaining target = 3
    -> [2, 2, 2], remaining target = 1 (exceeds any single element, backtrack)
    -> [2, 2, 3], exact match, print [2, 2, 3]

3. Continue with Other Elements:

   • After exploring all possibilities starting with 2, move to 3, then 6, then 7.

Trying [3], remaining target = 4
  -> [3, 3], remaining target = 1 (no match, backtrack)
Trying [6], remaining target = 1 (no match, backtrack)
Trying [7], exact match, print [7]

4. Final Output:

   • The valid combinations are: [[2, 2, 3], [7]]

This solution efficiently finds all combinations using recursion and backtracking, ensuring that every possibility is explored while avoiding unnecessary calculations when the remaining target becomes too small.

19. Distinct Permutations of an Array:

To generate all distinct permutations of an array that may contain duplicates, the backtracking approach can be optimized by first sorting the array. This helps to easily skip over duplicates when generating permutations. Using a boolean array to track which elements have been used in the current recursion level prevents reusing the same element in the same permutation position and avoids duplicates in the output.

Approach Using Backtracking and Sorting

1. Understanding the Problem: The objective is to generate permutations of an array containing duplicates such that no permutation is repeated.

2. Optimized Backtracking Technique:

   • Sort the Array: Begin by sorting the array to bring duplicates together. This makes it easier to skip duplicates during the permutation process.

   • Backtracking with State Tracking: Use a recursive function to generate permutations. Use a boolean array to mark elements that are included in the current permutation to avoid using the same element twice.

   • Skip Duplicates: When backtracking, skip over adjacent duplicate elements to ensure unique permutations.

3. Implementation Steps:

   • Sort the array.

   • Use a recursive function with an additional boolean array to track which elements are already used in the permutation being constructed.

   • At each recursive call, consider elements that are not yet used and are not duplicates of the previously considered element unless the duplicate was used in the previous step.

Implementation

#include <stdio.h>
#include <stdlib.h>

// Function to swap elements in the array
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Utility function to print an array
void printArray(int arr[], int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(", ");
    }
    printf("], ");
}

// Recursive function to generate distinct permutations
void permute(int arr[], int start, int n, int *used) {
    if (start == n) {
        printArray(arr, n);
        return;
    }

    for (int i = start; i < n; i++) {
        // Skip duplicates
        if (used[i] || (i > start && arr[i] == arr[i - 1] && !used[i - 1]))
            continue;

        used[i] = 1; // Mark this element as used
        swap(&arr[start], &arr[i]); // Swap to fix this element at the current position
        permute(arr, start + 1, n, used); // Recursively permute the rest
        swap(&arr[start], &arr[i]); // Backtrack
        used[i] = 0; // Unmark this element
    }
}

// Function to sort the array - simple insertion sort
void sortArray(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {1, 2, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    sortArray(arr, n); // Sort the array first to handle duplicates

    int *used = calloc(n, sizeof(int)); // Boolean array to keep track of used elements
    printf("Distinct permutations are:\n[");
    permute(arr, 0, n, used);
    printf("]\n");

    free(used); // Free the used array
    return 0;
}

Example and Explanation

Given the sorted input array {1, 2, 2}:

1. Initial Setup:

   • The array is sorted: [1, 2, 2].

   • Use a boolean array [0, 0, 0] to track used elements.

2. Recursive Exploration:

   • Start with the first element 1:

Fix 1:
[1, 2, 2]  // Permute [2, 2]

• Then try with 2 from position 1 and skip the duplicate 2 from position 2 during this call:

Fix 2 (first occurrence):
[2, 1, 2]  // Permute [1, 2]
Fix 2 (second occurrence):
[2, 2, 1]  // Permute [2, 1]

3. Backtracking:

   • Backtrack to try the next set of permutations, ensuring that duplicates are skipped if not used in the permutation set.

Backtrack after each completion to try next potential permutations.

The output of the program is Distinct permutations are: [[1, 2, 2], [2, 1, 2], [2, 2, 1], ], effectively listing all unique permutations while avoiding duplicates through careful management of element use and skipping. This approach ensures each permutation is unique by managing how elements are chosen and backtracked with the use of the used array and duplicate checks.

20. Combinations Sum II:

To solve the "Combination Sum II" problem, where you must find all unique combinations in a given array that sum to a target number ( T ) with each number used only once, a combination of sorting, backtracking, and careful element choice is required to ensure unique solutions, especially given potential duplicates in the input.

Approach Using Recursive Backtracking and Sorting

1. Understanding the Problem: The aim is to find unique sets of numbers that sum to a target value. Numbers in the candidate list can be used at most once, and the candidate list might contain duplicates.

2. Strategy:

   • Sort the Array: Begin by sorting the array to bring duplicates together. This setup makes it easier to skip duplicates during the recursive process.

   • Backtracking with Constraints: Use a recursive function to build combinations. Add constraints to ensure that each number is used at most once, and skip subsequent duplicate numbers immediately following the number just used.

   • Skip Duplicates: When starting a new recursive call from a specific loop index, skip over adjacent elements that are duplicates of the current element to avoid repeating the same combination.

3. Implementation Steps:

   • Sort the array to handle duplicates effectively.

   • Use a recursive function to explore possible combinations, adding elements to a temporary list and recursively attempting to add further elements.

   • If a combination matches the target sum, add it to the result list.

   • After exploring with a number, backtrack by removing it from the current combination and proceed to the next number in the array, skipping duplicates.

Implementation

#include <stdio.h>
#include <stdlib.h>

// Utility function to print array
void printArray(int arr[], int size) {
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(", ");
    }
    printf("]");
}

// Function to perform the combination sum search
void findCombinations(int arr[], int n, int start, int target, int* combo, int comboSize, int** results, int* resultSize, int* colSizes) {
    if (target == 0) { // Combination is found
        results[*resultSize] = (int*) malloc(comboSize * sizeof(int));
        for (int i = 0; i < comboSize; i++) {
            results[*resultSize][i] = combo[i];
        }
        colSizes[*resultSize] = comboSize;
        (*resultSize)++;
        return;
    }

    for (int i = start; i < n; i++) {
        if (i > start && arr[i] == arr[i - 1]) continue; // Skip duplicates
        if (arr[i] > target) break; // No need to continue if the current number is greater than the remaining target

        combo[comboSize] = arr[i];
        findCombinations(arr, n, i + 1, target - arr[i], combo, comboSize + 1, results, resultSize, colSizes);
    }
}

// Function to sort array
void sortArray(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {10, 1, 2, 7, 6, 1, 5};
    int target = 8;
    int n = sizeof(arr) / sizeof(arr[0]);

    // Sorting the array
    sortArray(arr, n);

    // Prepare for backtracking
    int* combo = (int*) malloc(target * sizeof(int));
    int** results = (int**) malloc(100 * sizeof(int*)); // Assuming a max of 100 combinations
    int* colSizes = (int*) malloc(100 * sizeof(int));
    int resultSize = 0;

    // Find combinations
    findCombinations(arr, n, 0, target, combo, 0, results, &resultSize, colSizes);

    // Print results
    printf("Unique combinations are: [");
    for (int i = 0; i < resultSize; i++) {
        printArray(results[i], colSizes[i]);
        if (i < resultSize - 1) printf(", ");
    }
    printf("]\n");

    // Free allocated memory
    for (int i = 0; i < resultSize; i++) free(results[i]);
    free(results);
    free(colSizes);
    free(combo);

    return 0;
}

Example and Explanation

Given the sorted input array [1, 1, 2, 5, 6, 7, 10] and a target of 8:

1. Initial Setup:

   • The array is first sorted to [1, 1, 2, 5, 6, 7, 10].

   • Begin searching for combinations starting from index 0.

2. Recursive Exploration:

   • Start with the first 1 and attempt to build up to 8.

   • Continue exploring deeper with subsequent elements, skipping over the second 1 when the first has been included.

3. Skipping Duplicates:

   • When encountering the second 1, skip it if the first 1 was used, preventing duplicate combinations like [1, 1, 6] and [1, 1, 6] repeated.

4. Successful Combinations:

   • The combinations that meet the target are: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]].

This solution efficiently ensures that each combination is unique and meets the target, utilizing sorting and careful handling of duplicates during the recursive process.