5 hours ago

ANIRUDH • 0

Kota

Problem 1: Merge Sorted Arrays

What is the question asking? The problem requires you to take two integer arrays, both of which are already sorted in non-decreasing order, and merge them into a single, new array that contains all elements from both inputs, also in non-decreasing sorted order.  

Solution: Two-Pointer Linear Merge The most efficient solution is to use a two-pointer technique, which is the fundamental operation in the Merge Sort algorithm. This approach avoids a costly re-sorting of the combined array by intelligently building the final array in a single pass. It iterates through both input arrays, comparing the elements at the current pointers and appending the smaller of the two to the result array. This leverages the pre-sorted nature of the inputs to achieve optimal linear time complexity.  

The logic is as follows:

• Allocate Result Array: Create a new array, result, with a size large enough to hold all elements from both input arrays (a and b).

• Initialize Pointers: Set up three index pointers: i for array a, j for array b, and k for the result array. All start at 0.

• Main Merge Loop: While there are still elements to be processed in both a and b (i.e., i < a.size() and j < b.size()):

  • Compare a[i] and b[j].

  • If a[i] is less than or equal to b[j], copy a[i] to result[k], then increment i and k.

  • Otherwise, copy b[j] to result[k], then increment j and k.

• Copy Remaining Elements: After the main loop finishes, one of the input arrays will be exhausted, but the other may still contain elements. A separate loop is used to copy all remaining elements from the non-empty array to the end of result.

• Return Final Array: The result array, now containing all elements from a and b in sorted order, is returned.

#include <iostream>
#include <vector>
#include <string>

std::vector<int> mergeArrays(const std::vector<int>& a, const std::vector<int>& b) {
    int n = a.size();
    int m = b.size();
    std::vector<int> result(n + m);

    int i = 0;
    int j = 0;
    int k = 0;

    while (i < n && j < m) {
        if (a[i] <= b[j]) {
            result[k] = a[i];
            i++;
        } else {
            result[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < n) {
        result[k] = a[i];
        i++;
        k++;
    }

    while (j < m) {
        result[k] = b[j];
        j++;
        k++;
    }

    return result;
}

Complexity Analysis:

• Time Complexity: O(n+m). The algorithm makes a single pass through the input arrays. Each element from both arrays is examined and copied exactly once, leading to a linear runtime proportional to the total number of elements.  

• Space Complexity: O(n+m). The problem requires the creation of a new array to store the merged result. The space required is therefore proportional to the total number of elements.  

5 hours ago

ANIRUDH • 0

Kota

Problem 2: Analogous Arrays

What is the question asking? The problem asks you to calculate the total number of arrays that are "analogous" to a secret array. An array is analogous if its elements are within a given lowerBound and upperBound and the differences between its consecutive elements are identical to those of the secret array, which are provided in the consecutiveDifference input array.  

Solution: Mathematical Range Calculation The key insight is that the consecutiveDifference array rigidly defines the structure of any analogous array. Once the first element is chosen, all subsequent elements are fixed. This transforms the problem from counting arrays to counting the number of valid choices for the first element. The solution calculates the array's shape relative to a starting value of 0, finds its relative minimum and maximum, and then determines how many integer starting positions allow this fixed shape to fit entirely within the lowerBound and upperBound constraints.  

The logic is as follows:

• Determine Relative Shape: Imagine an array template where the first element is 0. Calculate the values of all other elements based on the consecutiveDifference array.

• Find Relative Extrema: In a single pass through the consecutiveDifference array, calculate the minimum (min_val) and maximum (max_val) values this template array would have, relative to its starting point of 0.

• Establish Bounds for the First Element: Let the true starting element be start_val. For the entire array to be valid, two conditions must be met:

  • The lowest point of the array, start_val + min_val, must be >= lowerBound.

  • The highest point of the array, start_val + max_val, must be <= upperBound.

• Calculate Valid Range: Rearrange the inequalities to solve for the valid range of start_val:

  • start_val >= lowerBound - min_val

  • start_val <= upperBound - max_val

• Count Solutions: The number of possible analogous arrays is the number of integers in this calculated range. If the lower end of the range is greater than the upper end, no solutions exist, and the answer is 0. Otherwise, the count is (upper_end - lower_end + 1).

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

int countAnalogousArrays(const std::vector<int>& consecutiveDifference, int lowerBound, int upperBound) {
    long long current_val = 0;
    long long min_val = 0;
    long long max_val = 0;

    for (int diff : consecutiveDifference) {
        current_val -= diff;
        min_val = std::min(min_val, current_val);
        max_val = std::max(max_val, current_val);
    }

    long long valid_start_min = lowerBound - min_val;
    long long valid_start_max = upperBound - max_val;

    if (valid_start_min > valid_start_max) {
        return 0;
    }

    return static_cast<int>(valid_start_max - valid_start_min + 1);
}

Complexity Analysis:

• Time Complexity: O(N). The solution involves a single pass through the consecutiveDifference array of length N to determine the relative shape and extrema.  

• Space Complexity: O(1). The algorithm uses a fixed number of variables to track the current relative value, minimum, and maximum. Memory usage does not scale with the input size.  

5 hours ago

ANIRUDH • 0

Kota

Problem 3: Maximum Score of a Balanced Subsequence

What is the question asking? The problem asks you to find the maximum possible score from a "balanced" subsequence of an array of stock prices. The score is the sum of the prices in the subsequence. A subsequence is balanced if for any two consecutive chosen items, the difference in their prices is equal to the difference in their original array indices.  

Solution: Algebraic Transformation and Hashing The most effective solution relies on a key algebraic insight. The balance condition stockPrice[j] - stockPrice[i] = j - i can be rearranged to stockPrice[j] - j = stockPrice[i] - i. This reveals a powerful invariant: all elements in a balanced subsequence must have the same value for the expression price - index. The problem is thus transformed into grouping all elements by this invariant key, summing the prices within each group, and finding the group with the largest total sum.  

The logic is as follows:

• Initialize a Hash Map: Use a hash map (like std::unordered_map) to store the sum of scores for each group. The map's key will be the invariant stockPrice[i] - i, and the value will be the running sum of prices for that key.

• Group and Sum: Iterate through the stockPrice array with index i.

  • For each element stockPrice[i], calculate the key: key = stockPrice[i] - i.

  • Add the current stockPrice[i] to the sum associated with that key in the hash map.

• Find Maximum Score: After populating the map, iterate through all the summed values in the map to find the maximum score.

• Handle Single-Element Case: A subsequence of length 1 is always balanced. The final answer must be at least the largest single stock price in the original array. The result is the maximum of the best group score and the highest individual price.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

long getMaximumScore(const std::vector<int>& stockPrice) {
    if (stockPrice.empty()) {
        return 0;
    }

    std::unordered_map<int, long> scores;
    long max_score = 0;
    bool first = true;

    for (int i = 0; i < stockPrice.size(); ++i) {
        int key = stockPrice[i] - i;
        scores[key] += stockPrice[i];
    }

    for (auto const& [key, val] : scores) {
        if (first) {
            max_score = val;
            first = false;
        } else {
            max_score = std::max(max_score, val);
        }
    }

    for (int price : stockPrice) {
        max_score = std::max(max_score, (long)price);
    }

    return max_score;
}

Complexity Analysis:

• Time Complexity: O(N). The algorithm requires a single pass through the stockPrice array of size N to populate the hash map. Hash map lookups and insertions take average $O(1)$ time.  

• Space Complexity: O(M). The space is determined by the number of unique keys (M) stored in the hash map. In the worst case, every element produces a unique key, leading to $O(N) space complexity.