algoadvance

Leetcode 2574. Left and Right Sum Differences

Problem Statement

Given a 1-indexed integer array nums, you are asked to return an array answer of length n where answer[i] is the absolute difference between the sum of elements to the left of index i and the sum of elements to the right of index i.

More formally, answer[i] = |leftSum[i] - rightSum[i]|.

Where:

Clarifying Questions

  1. Indexing: The problem states the array is 1-indexed, but typical C++ arrays are 0-indexed. Should the solution follow usual 0-indexing for ease?
    • Yes, the problem will be solved using 0-indexed arrays for simplicity and converted if necessary.
  2. Edge Cases: What are the constraints on the input array size and element values?
    • Constraints are typically provided in the problem statement. We will assume reasonable constraints (e.g., up to (10^5) elements in the array).

Strategy

  1. Initialize Prefix and Suffix Sums:
    • Compute prefix sum as we iterate through the array to get the left sum for each index.
    • Compute the total sum of the array beforehand.
  2. Compute Right Sums Efficiently:
    • As we are computing answer while iterating, compute the right sum by subtracting the prefix sum from the total sum for each index.
Given leftSum[i] and rightSum[i], compute the absolute difference ( leftSum[i] - rightSum[i] ).

Code

#include <vector>
#include <cmath>
#include <iostream>

std::vector<int> leftRightDifference(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> answer(n);
    std::vector<int> prefixSum(n, 0);
    
    // Compute prefix sum
    prefixSum[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }
    
    // Compute the total sum of the array
    int totalSum = prefixSum[n - 1];
    
    // Compute the result
    for (int i = 0; i < n; ++i) {
        int leftSum = (i == 0) ? 0 : prefixSum[i - 1];
        int rightSum = totalSum - prefixSum[i];
        answer[i] = std::abs(leftSum - rightSum);
    }
    
    return answer;
}

// Helper function to print the vector
void printVector(const std::vector<int>& vec) {
    std::cout << "[ ";
    for (const int& value : vec) {
        std::cout << value << " ";
    }
    std::cout << "]" << std::endl;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::vector<int> result = leftRightDifference(nums);
    printVector(result);
    return 0;
}

Time Complexity

Thus, the overall time complexity is O(n), where (n) is the number of elements in the input array.

This solution is efficient and handles the constraints effectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI