Lets Code Everyday - Day 19

Question - 19:

Left and Right Sum Differences

Given a 0-indexed integer array nums, find a 0-indexed integer array answer where:

• answer.length == nums.length.

• answer[i] = |leftSum[i] - rightSum[i]|.

Where:

• leftSum[i] is the sum of elements to the left of the index i in the array nums. If there is no such element, leftSum[i] = 0.

• rightSum[i] is the sum of elements to the right of the index i in the array nums. If there is no such element, rightSum[i] = 0.

Return the array answer.

Example 1:

Input: nums = [10,4,8,3]
Output: [15,1,11,22]
Explanation: The array leftSum is [0,10,14,22] and the array rightSum is [15,11,3,0].
The array answer is [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22].

Example 2:

Input: nums = [1]
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0].
The array answer is [|0 - 0|] = [0].

First approach:

class Solution {
    public int[] leftRigthDifference(int[] nums) {
        int[] res= new int[nums.length];
        for(int i=0;i<nums.length;i++){
            int rightSum=0; int leftSum=0;
            for(int j=0;j<nums.length;j++){
                if(j>i) rightSum=rightSum+nums[j];
                else if(j<i) leftSum=leftSum+nums[j];
            }
            res[i]=Math.abs(rightSum-leftSum);
        }
     return res;   
    }
}

Step-by-step implementation:

1. The method takes an integer array nums as its input parameter and creates an empty integer array res with the same length as nums.

2. The method iterates over each element of the nums array using a for loop. For each element, it calculates the sum of all the elements to the right and left of that element separately.

3. To calculate the sum of the elements to the right and left of the current element, the method uses another nested for loop that iterates over all the elements of the nums array again.

4. If the current index j of the nested loop is greater than the index i of the element being considered in the outer loop, then the value at the index j is added to the rightSum variable.

5. If the current index j is less than the index i of the element being considered, then the value at the index j is added to the leftSum variable.

6. Once the inner loop completes, the absolute difference between the rightSum and leftSum variables is calculated using the Math.abs() method and stored in the corresponding index of the res array.

7. The outer loop repeats this process for each element of the nums array, storing the absolute difference between the sum of all the elements to the right and left of each element in the corresponding index of the res array.

8. Once all elements of the nums array have been processed, the res array is returned by the method.

The time complexity of the leftRigthDifference method is O(n^2), where n is the length of the input array nums. This is because the method uses a nested for loop to iterate over all elements of the nums array twice, resulting in a time complexity of O(n^2).

The space complexity of the leftRigthDifference method is O(n), where n is the length of the input array nums. This is because the method creates a new integer array res of the same length as nums to store the absolute differences between the sums of the elements to the left and right of each element in the nums array. Therefore, the space complexity of the method is directly proportional to the size of the input array nums.

Second approach:

class Solution {
    public int[] leftRigthDifference(int[] nums) {
      int[] res = new int[nums.length];
      int sum = 0;
      for (int num : nums) {
         sum += num;
      }
      int leftSum = 0;
      for (int i = 0; i < nums.length; i++) {
         res[i] = Math.abs(sum - leftSum - nums[i] - leftSum);
         leftSum += nums[i];
      }
    return res; 
    }
}

Step-by-step implementation:

1. Create a new integer array res of length nums.length to store the absolute differences between the sums of the elements to the left and right of each element in the nums array.

2. Initialize a variable sum to zero.

3. Iterate over all elements of the nums array using a loop: a. In each iteration, add the current element nums[i] to the sum variable.

4. Initialize a variable leftSum to zero.

5. Iterate over all elements of the nums array using a loop: a. In each iteration, calculate the absolute difference between the sum of the elements to the left and right of the current element nums[i] using the formula Math.abs(sum - leftSum - nums[i] - leftSum). b. Store the result in the res array at the corresponding index i. c. Add the value of nums[i] to the leftSum variable.

6. Return the res array.

The time complexity of the refactored code is O(n), where n is the length of the nums array. This is because the code iterates over the nums array twice: once to calculate the total sum of all elements in the array, and once to calculate the absolute difference between the sum of the elements to the left and right of each element. Since these operations take constant time, the time complexity of the entire algorithm is linear in the length of the input array.

The space complexity of the refactored code is O(n), where n is the length of the nums array. This is because the code creates a new integer array res of length n to store the absolute differences between the sums of the elements to the left and right of each element in the nums array. In addition, the code uses a constant amount of extra space for the sum and leftSum variables. Therefore, the space complexity of the entire algorithm is linear in the length of the input array.

Conclusion:

In terms of performance, the second approach is better than the first approach. The first approach had a time complexity of O(n^2) because it had a nested loop that iterated over the nums array for every element, resulting in a quadratic time complexity. The second approach, on the other hand, has a time complexity of O(n) because it only iterates over the nums array twice: once to calculate the total sum of all elements, and once to calculate the absolute differences between the sums of the elements to the left and right of each element. This results in a linear time complexity, which is more efficient than the first approach.

In terms of space complexity, both codes have the same O(n) space complexity because they both create a new array of size n to store the results. However, the second approach uses less space than the first approach because it only creates one extra variable (leftSum) to keep track of the running total of the sum of elements to the left of the current element, while the first approach creates two extra variables (leftSum and rightSum) to keep track of the running totals of the sums of elements to the left and right of the current element.

Thanks for reading...Happy learning....😁