Arrays (Level-2)

1. Range sum queries using prefix sum

Description : We are given an Array of n integers, We are given q queries having indices l and r .
 We have to find out sum between the given range of indices.
Input 
[4, 5, 3, 2, 5]
3
0 3
2 4
1 3
Output
14 (4+5+3+2)
10 (3+2+5)
10 (5+3+2)
-----------------------------------
// n : size of array
// q : Number of queries
// l, r : Finding Sum of range between index l and r 
// l and r (inclusive) and 0 based indexing
void range_sum(arr, n)
{
    prefix[n] = {0}
    prefix[0] = arr[0]
    for i = 1 to n-1 :
        prefix[i] = a[i] + prefix[i-1]

    for (i = 1 to q )
    {
        if (l == 0) 
        {
            ans = prefix[r]
            print(ans)
        }
        else 
        {
            ans = prefix[r] - prefix[l-1]
            print(ans)
        }
    }
}
Time Complexity : Max(O(n),O(q))
Auxiliary Space : O(n)

2. Equilibrium Index of array

Description - Equilibrium index of an array is an index such that the sum of elements 
at lower indexes is equal to the sum of elements at higher indexes. 
We are given an Array of integers, We have to find out the first index i from left such that -
A[0] + A[1] + ... A[i-1] = A[i+1] + A[i+2] ... A[n-1]
--------------------
Input
[-7, 1, 5, 2, -4, 3, 0]
Output
3
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
----------------------
// n : size of array
int eqindex(arr, n)
{
    sum = 0
    leftsum = 0
    for (i=0 to n-1)
        sum += arr[i]

    for (i=0 to n-1)
    {
        // now sum will be righsum for index i
        sum -= a[i]
        if (sum == leftsum )
            return i
        leftsum += a[i]
    }
}


Time Complexity : O(n)
Auxiliary Space : O(1)

3. Largest sum subarray

Description : We are given an array of positive and negative integers. We have to find the subarray having maximum sum.
Input
[-3, 4, -1, -2, 1, 5]
Output
7
(4+(-1)+(-2)+1+5)
-----------------------
//n : size of array
int largestsum(arr, n)
{
    max_so_far = INT_MIN
    max_ending_here = 0

    for (i=0 to n-1)
    {
        max_ending_here += arr[i]
        if max_so_far < max_ending_here :
            max_so_far = max_ending_here

        if max_ending_here < 0 :
            max_ending_here = 0
    }

    return max_so_far
}


Time Complexity : O(n)
Auxiliary Space : O(1)

4. Merge two sorted array

Description : We are given two sorted arrays arr1[ ] and arr2[ ] 
of size m and n respectively. We have to merge these arrays and store 
the numbers in arr3[ ] of size m+n.
Input
1 3 4 6
2 5 7 8
Output
1 2 3 4 5 6 7 8
-----------------------------------------
// input arrays - arr1(size m), arr2(size n)
void merge_sorted(arr1, arr2, m, n)
{
    arr3[m+n] // merged array
    i=0,j=0,k=0
    while(i < m && j < n) 
    {
        if arr1[i] < arr2[j] :
            arr3[k++] = arr1[i++]
        else :
            arr3[k++] = arr2[j++]
    }
    while(i < m)
        arr3[k++] = arr1[i++]
    while(j < n)
        arr3[k++] = arr2[j++]
}


Time Complexity : O(m+n)
Auxiliary Space : O(m+n)

5. Left and right rotate by k places

#include <bits/stdc++.h>
using namespace std;

// Utility: reverse elements in [l, r]
void reverseArray(vector<int>& arr, int l, int r) {
    while (l < r) {
        swap(arr[l], arr[r]);
        l++;
        r--;
    }
}

// Left Rotate by k places
void leftRotate(vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0) return;
    k = k % n; // handle k > n
    if (k == 0) return;

    reverseArray(arr, 0, k - 1);     // reverse first k
    reverseArray(arr, k, n - 1);     // reverse remaining
    reverseArray(arr, 0, n - 1);     // reverse whole
}

// Right Rotate by k places
void rightRotate(vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0) return;
    k = k % n; // handle k > n
    if (k == 0) return;

    reverseArray(arr, 0, n - 1);     // reverse whole
    reverseArray(arr, 0, k - 1);     // reverse first k
    reverseArray(arr, k, n - 1);     // reverse remaining
}

6. Frequencies in sorted array

void printFreq(vector<int>& arr, int N)
{
    // Stores the frequency of an element
    int freq = 1;
    // Traverse the array arr[]
    for (int i = 1; i < N; i++) {
        // If the current element is equal
        // to the previous element
        if (arr[i] == arr[i - 1]) {
            // Increment the freq by 1
            freq++;
        }
       // Otherwise,
        else {
            cout << "Frequency of " << arr[i - 1]
                 << " is: " << freq << endl;
            // Update freq
            freq = 1;
        }
    }
    // Print the frequency of the last element
    cout << "Frequency of " << arr[N - 1] << " is: " << freq
         << endl;
}

7. Stock buy and sell

int maxProfit(int price[], int n)
{
    int profit = 0;

    for(int i = 1; i < n; i++)
    {
        if(price[i] > price[i - 1])
            profit += price[i] - price[i -1];
    }

    return profit;

}

8. Max subarray sum

void SubarrayWithMaxSum(vector<int>& nums)
{
    // Initialize currMax and globalMax
    // with first value of nums
    int endIndex, currMax = nums[0];
    int globalMax = nums[0];

    // Iterate for all the elements
    // of the array
    for (int i = 1; i < nums.size(); ++i) {

        // Update currMax
        currMax = max(nums[i],
                    nums[i] + currMax);

        // Check if currMax is greater
        // than globalMax
        if (currMax > globalMax) {
            globalMax = currMax;
            endIndex = i;
        }
    }

    int startIndex = endIndex;

    // Traverse in left direction to
    // find start Index of subarray
    while (startIndex >= 0) {

        globalMax -= nums[startIndex];

        if (globalMax == 0)
            break;

        // Decrement the start index
        startIndex--;
    }

    // Printing the elements of
    // subarray with max sum
    for (int i = startIndex;
        i <= endIndex; ++i) {

        cout << nums[i] << " ";
    }
}

9. Longest even odd subarray

int maxEvenOdd(int arr[], int n)
{
    if (n == 0)
        return 0;

    int maxLength = 1;  // Start with a minimum length of 1
    int currLen = 1;    // Current alternating sequence length

    for (int i = 1; i < n; i++) {
        // Check if the current element is alternating with the previous one
        if (arr[i] % 2 != arr[i - 1] % 2) {
            currLen++;  // Continue the alternating sequence
        } else {
            maxLength = max(maxLength, currLen);  // Update maxLength if needed
            currLen = 1;  // Reset current sequence length
        }
    }
    // Final check for the last sequence
    maxLength = max(maxLength, currLen);

    // If maxLength is 1, no valid alternating subarray exists
    if (maxLength == 1)
        return 0;
    return maxLength;
}

10. Max circular sum subarray

nput: arr[] = {8, -8, 9, -9, 10, -11, 12}
Output: 22 
Explanation: Subarray 12, 8, -8, 9, -9, 10 gives the maximum sum, that is 22.

Input: arr[] = {10, -3, -4, 7, 6, 5, -4, -1} 
Output:  23 
Explanation: Subarray 7, 6, 5, -4, -1, 10 gives the maximum sum, that is 23.
----------------------
int normalMaxSum(int arr[], int n)
{
    int res = arr[0];

    int maxEnding = arr[0];

    for(int i = 1; i < n; i++)
    {
        maxEnding = max(maxEnding + arr[i], arr[i]);

        res = max(maxEnding, res);
    }

    return res;
}

int overallMaxSum(int arr[], int n)
{
    int max_normal = normalMaxSum(arr, n);

    if(max_normal < 0)
        return max_normal;

    int arr_sum = 0;

    for(int i = 0; i < n; i++)
    {
        arr_sum += arr[i];

        arr[i] = -arr[i];
    }

    int max_circular = arr_sum + normalMaxSum(arr, n);

    return max(max_circular, max_normal);
}

11. Sliding window

Our Task: Given an array of integers of size 'n'. Our aim is to calculate the maximum sum of 
'k' consecutive elements in the array.
Input  : arr[] = {100, 200, 300, 400}
         k = 2
Output : 700

Input  : arr[] = {1, 4, 2, 10, 23, 3, 1, 0, 20}
         k = 4 
Output : 39
We get maximum sum by adding subarray {4, 2, 10, 23}
of size 4.
--------------
// Returns maximum sum in a subarray of size k.
int maxSum(int arr[], int n, int k)
{
    // n must be greater
    if (n < k) {
        cout << "Invalid";
        return -1;
    }

    // sum of first window of size k
    int window_sum = 0;
    for (int i = 0; i < k; i++)
        window_sum += arr[i];

    // Compute sums of remaining windows by
    // removing first element of previous
    // window and adding last element of
    // current window.
    int max_sum = window_sum;
    for (int i = k; i < n; i++) {
        window_sum += (arr[i] - arr[i - k]);
        max_sum = max(max_sum, window_sum);
    }
    return max_sum;
}

12) Prefix Sum technique

Given an array arr[] of size n, its prefix sum array is another array prefixSum[] of the same size, 
such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] … arr[i].

Examples : 
Input  : arr[] = {10, 20, 10, 5, 15}
Output : prefixSum[] = {10, 30, 40, 45, 60}
Explanation : While traversing the array, update the element by adding it with its previous element.
prefixSum[0] = 10, 
prefixSum[1] = prefixSum[0] + arr[1] = 30, 
prefixSum[2] = prefixSum[1] + arr[2] = 40 and so on.
------------------------------
int getSum(int l, int r, vector<int>& pSum) {
    if (l == 0)
        return pSum[r];
    else
        return pSum[r] - pSum[l - 1];
}

int main() {
    vector<int> arr = {2, 8, 3, 9, 6, 5, 4};
    int n = arr.size();

    vector<int> pSum(n);
    pSum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        pSum[i] = pSum[i - 1] + arr[i];
    }

    cout << getSum(2, 6, pSum) << endl; // sum from index 2 to 6
    return 0;
}