Shipment Imbalance Amazon OA 2023

Contents

1 Shipment Imbalance Solution
- 1.1 SOLUTION
2 Amazon OA 2023 Questions with Solution

Shipment Imbalance Solution

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3]

Output: 4

Explanation:

The 6 subarrays of nums are the following:

[1], range = largest – smallest = 1 – 1 = 0
[2], range = 2 – 2 = 0
[3], range = 3 – 3 = 0
[1,2], range = 2 – 1 = 1
[2,3], range = 3 – 2 = 1
[1,2,3], range = 3 – 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.

Example 2:

Input: nums = [1,3,3]

Output: 4

Explanation:

The 6 subarrays of nums are the following:

[1], range = largest – smallest = 1 – 1 = 0
[3], range = 3 – 3 = 0
[3], range = 3 – 3 = 0
[1,3], range = 3 – 1 = 2
[3,3], range = 3 – 3 = 0
[1,3,3], range = 3 – 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.

Example 3:

Input: nums = [4,-2,-3,4,1]

Output: 59

Explanation: The sum of all subarray ranges of nums is 59.

Constraints:

1 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

SOLUTION

Program: Shipment Imbalance Solution in Python

Basically you maintain two heaps max and min and loop to get the subarrays. For each subarray you add the elements to the heap and peek at max and min heap at each step to get the difference and add to answer. As soon as you have exhausted all possibilities for an index you reset both the heaps and move forward.

Example
123

You start with 1, since 1 is max and 1 is min therfore the diff is 0, we don’t need to do anything here but we add the number to the heaps, then next sequence starting from 1 is 12 therefore we add 2 to the heap and see whats the min and max and add their difference to the ans and so on.

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        result = 0
        n = len(nums)
        for i in range(n) :
            Min, Max = nums[i], nums[i]
            
            for j in range(i, n, 1) :
                Min = min(Min, nums[j])
                Max = max(Max, nums[j])
                result -= Max - Min
            
        return abs(result)

Program: Shipment Imbalance Solution in C++

Approach 1 – By considering every subsegment (Brute Force):

We will discover every possible subsegment while storing the minimum and maximum elements.
Also, we will keep adding the difference between the maximum and minimum values in every iteration.

#include <iostream>
#include <vector>
using namespace std;
long ValueOfA(int n, vector<int> &A)
{
    long ans = 0;
    for (int i = 0; i < n; i++)
    {
        int mx = A[i], mn = A[i];
        for (int j = i + 1; j < n; j++)
        {
            mx = max(mx, A[j]);
            mn = min(mn, A[j]);
            ans += (mx - mn);
        }
    }
    return ans;
}
int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++)
        cin >> A[i];
    cout << ValueOfA(n, A);
}

Time Complexity – O(n^2) – As we are just iterating n times for every element. [where n is the length of the array].
Space Complexity – O(1) – As we just used 2 extra variables for storing maximum and minimum values, and no extra space.

Approach 2 – By finding The Next Greater and Next Smaller Elements on left and right (Optimized):

We will take the contribution of each element as addition/subtraction in the final answer.
Standing on an element, if we see on the subsegments going on the right-hand side of it, the element will act as the minimum, till the elements are greater than it; i.e we need to find the next just smaller element than the current element on the right-hand side of it.
Similarly, it will act as the maximum, till the elements are smaller than it; i.e we need to find the next just greater element than the current element on the right-hand side of it.
The same is the case with the left-hand side.
Thus for a particular element, we will store the count of elements that are smaller, and that are greater; for both the left-hand side and the right-hand side.
As we know the counts, then for a particular element we will add to the final answer – [currentElement * cgl * cgr]. As this will be the contribution of the current element being as a maximum in all the subsegments, in which it is occurring.
Similarly, for a particular element we will subtract from the final answer – [currentElement * csl * csr]. As this will be the contribution of the current element being as a minimum in all the subsegments, in which it is occurring.

This can be done using stacks. We will store the indices of elements in the stack.
For finding the count of greater elements on left (cgl) and count of greater elements on right (cgr), we will keep popping the elements in the stack until it is not empty and the top element of the stack is less than or equal to the current element.
So the current element will be the next greater element on the right of all the elements that are popped, and the difference between their positions will be the value of cgr for all the popped elements.
And the current top element of the stack, due to which the popping was stopped will be the next greater element on left for the current element, and the difference between their positions will be the value of cgl for the current element.
Similarly, for finding the count of smaller elements on left (csl) and count of smaller elements on right (csr), we will keep popping the elements in the stack until it is not empty and the top element of the stack is greater than or equal to the current element.
So the current element will be the next smaller element on the right of all the elements that are popped, and the difference between their positions will be the value of csr for all the popped elements.
And the current top element of the stack, due to which the popping was stopped will be the next greater smaller on left for the current element, and the difference between their positions will be the value of csl for the current element.
The remaining elements in the stack will have the values of cgl, csl, cgr, csr, as the default initial values.
The default initial value of cgl and csl for every element will be their index + 1 (the count of elements before it, including itself). And the default initial value of cgr and csr for every element will be their n – 1 (the count of elements after it, including itself).

class Pair
{
public:
    int cgl, csl, cgr, csr;
    Pair()
    {
        this->cgl = 0;
        this->csl = 0;
        this->cgr = 0;
        this->csr = 0;
    }
};
void fill_cgl_cgr(int n, vector<int> &A, vector<Pair> &conf)
{
    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        while (!st.empty() && A[i] >= A[st.top()])
        {
            conf[st.top()].cgr = i - st.top();
            st.pop();
        }
        if (!st.empty())
            conf[i].cgl = i - st.top();
        st.push(i);
    }
}
void fill_csl_csr(int n, vector<int> &A, vector<Pair> &conf)
{
    stack<int> st;
    for (int i = 0; i < n; i++)
    {
        while (!st.empty() && A[i] <= A[st.top()])
        {
            conf[st.top()].csr = i - st.top();
            st.pop();
        }
        if (!st.empty())
            conf[i].csl = i - st.top();
        st.push(i);
    }
}
long long ValueOfA(int n, vector<int> &A)
{
    long long ans = 0;
    vector<Pair> conf(n);
    for (int i = 0; i < n; i++)
    {
        conf[i].cgl = i + 1;
        conf[i].csl = i + 1;
        conf[i].cgr = n - i;
        conf[i].csr = n - i;
    }
    fill_cgl_cgr(n, A, conf);
    fill_csl_csr(n, A, conf);
    for (int i = 0; i < n; i++)
        ans += A[i] * (((long long)conf[i].cgl * conf[i].cgr) - ((long long)conf[i].csl * conf[i].csr));
    return ans;
}
int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++)
        cin >> A[i];
    cout << ValueOfA(n, A);
}

Time Complexity – O(n) – As we are finding the values of cgl, cgr in linear time, and also the values of csl and csr in linear time. And then finding the contribution of each element in the linear time.

Space complexity – O(n) – As we are storing the values of cgl, cgr, csl, csr in a linear array of size n. And also the stack space of size n (maximum).

Test Cases:-

Input1: nums = [3,5,8,2]
Output1: 28

Explanation1:

For every element x, we will do the following:
x = 3 -> cgl = 1, cgr = 1, csl = 1, csr = 3 -> contribution = 3*(11 – 13) = -6
x = 5 -> cgl = 2, cgr = 1, csl = 1, csr = 2 -> contribution = 5*(21 – 12) = 0
x = 8 -> cgl = 3, cgr = 2, csl = 1, csr = 1 -> contribution = 8*(32 – 11) = 40
x = 2 -> cgl = 1, cgr = 1, csl = 4, csr = 1 -> contribution = 2*(11 – 41) = -6

So the sum of all values is = (-6) + 0 + 40 + (-6) = 28.

Input2: nums = [1,3,3,1,2]
Output2: 17

Explanation2:

For every element x, we will do the following:
x = 1 -> cgl = 1, cgr = 1, csl = 1, csr = 3 -> contribution = 1*(11 – 13) = -2
x = 3 -> cgl = 2, cgr = 1, csl = 1, csr = 1 -> contribution = 3*(21 – 11) = 3
x = 3 -> cgl = 3, cgr = 3, csl = 2, csr = 1 -> contribution = 3*(33 – 21) = 21
x = 1 -> cgl = 1, cgr = 1, csl = 4, csr = 2 -> contribution = 1*(11 – 42) = -7
x = 2 -> cgl = 2, cgr = 1, csl = 1, csr = 1 -> contribution = 2*(21 – 11) = 2

So the sum of all values is = (-2) + 3 + 21 + (-8) + 2 = 17.

(Note that just for cgr, csr values, we are also considering equal element as the next just greater/smaller element on the right)

Program: Shipment Imbalance Amazon OA Solution in Java

Let’s say the array is [3,1,2,4].
Subarrays will be:

Subarrays           Max-Min
[3]                 3 - 3	= 0
[3,1]				3 - 1	= 2
[3,1,2]				3 - 1	= 2
[3,1,2,4]			4 - 1	= 3
  [1]				1 - 1	= 0
  [1,2]				2 - 1	= 1
  [1,2,4]			4 - 1	= 3
	[2]				2 - 2	= 0
	[2,4]			4 - 2	= 2
	  [4]			4 - 4	= 0

Answer would be = 0+2+2+3+0+1+3+0+2+0 = 13

Let us calculate the total number of occurrences of maximum and minimum elements from these subarrays.

Maximum side occurrences: ——————– reference (1)
‘3’ occurred 3 times
‘1’ occurred 1 times
‘2’ occurred 2 times
‘4’ occurred 4 times

Minimum side occurrences: ——————– reference (2)
‘3’ occurred 1 times
‘1’ occurred 6 times
‘2’ occurred 2 times
‘4’ occurred 1 times

If we subtract the sum of total minimum value from the sum of total maximum value. Then also we can get the result right?
i.e.

Maximum side sum						Minimum side sum
(3*3) + (1*1) + 2*2) + (4*4)= 30		(3*1)+ (1*6) + (2*2) + (4*1) = 17

so, 30 – 17 = 13.

we can again reduce the problem.
Lets us consider the situation for occurences of 3.
We were getting,

Maximum side sum			Minimum side sum
(3*3) = 9					(3*1) = 3

ans = 9-3 = 6

If we just subtract the minimum occurrences of 3 from the maximum occurrences of 3 and then multiply the value of 3 i.e. 3. Than also we can get the same answer.
That is:

(Max occur – Min occur)*value

(3 – 1)*3

= 2*3 = 6
same answer right?

We can do the same for the whole array.
(3-1) * 3 + (1-6) * 1 + (2-2) * 2 + (4-1) * 4
=2 * 3 + (-5) * 1 + 0 * 2 + 3 * 4
=6 – 5 + 0 + 12
=13

So, now our question is how we can get the maximum/minimum occurrences of 3,4,2 or 1.
For this you refer to Leetcode 907. https://leetcode.com/problems/sum-of-subarray-minimums/
else, go through a short explaination:

To find the number of minimum occurrences, we need to find,
the elements greater than the current element on left (including itself) * the elements greater than the current element on right (including itself)

array is:
[3, 1, 2, 4]
greater than the current element from left:
[1, 2, 1, 1]
from right,
[1, 3, 2, 1]

so, to get the minimum occurrences’ count we need to multiply both the arrays’ elements for each position.
i.e.:
pos 0 (val = 3) occurrence = (1 * 1) = 1
pos 1 (val = 1) occurrence = (2 * 3) = 6
pos 2 (val = 2) occurrence = (1 * 2) = 2
pos 3 (val = 4) occurrence = (1 * 1) = 1
Match these values with reference (2), see they are same.

Similarly to find maximum occurrences we need do find the lesser element for each element.

array is:
[3, 1, 2, 4]
lesser than the current element from left:
[1, 1, 2, 4]
from right,
[3, 1, 1, 1]

And minimum occurrences’ would be:
pos 0 (val = 3) occurrence = (1 * 3) = 3
pos 1 (val = 1) occurrence = (1 * 1) = 1
pos 2 (val = 2) occurrence = (2 * 1) = 2
pos 3 (val = 4) occurrence = (4 * 1) = 4
Match with reference (1).

So, ultimately answer would be ,
(maximum occurrences – minimum occurrences)* value for each element.
((1 * 3)-(1 * 1))*3 + ((1 * 1)-(2 * 3))*1 + ((2 * 1)-(1 * 2))*2 + ((4 * 1)-(1 * 1))*4
=(3-1) * 3 + (1-6) * 1 + (2-2) * 2 + (4-1) * 4
=2 * 3 + (-5) * 1 + 0 * 2 + 3 * 4
=6 – 5 + 0 + 12
=13

We can use monotonic stack to get the lesser or greater values for each element.

Note:
If we get duplicate elements like [3, 1, 2, 4, 2], we need to go until we get <= element from the left and < element from the right or the vice versa.
Same for the generation of greater counts.

class Solution {
    class Node{
        long val, displace;
        Node(long val, long displace){
            this.val = val;
            this.displace = displace;
        }
    }
    public long subArrayRanges(int[] nums) {
        
        //lesser than current element
        Stack<Node> stack = new Stack<>();
        //from left
        long [] lesserLeft = new long[nums.length];
        for (int i = 0; i< nums.length; i++){
            long count = 1;
            while(stack.size()>0 && stack.peek().val<=nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            lesserLeft[i] = count;
        }
        stack.clear();
        //from right
        long[] lesserRight = new long[nums.length];
        for (int i = nums.length-1; i>=0; i--){
            long count = 1;
            while(stack.size()>0 && stack.peek().val<nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            lesserRight[i] = count;
        }
        
        
        //greater than current element
        stack.clear();
        //from left
        long [] greaterLeft = new long[nums.length];
        for (int i = 0; i< nums.length; i++){
            long count = 1;
            while(stack.size()>0 && stack.peek().val>=nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            greaterLeft[i] = count;
        }
        stack.clear();
        //from right
        long[] greaterRight = new long[nums.length];
        for (int i = nums.length-1; i>=0; i--){
            long count = 1;
            while(stack.size()>0 && stack.peek().val>nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            greaterRight[i] = count;
        }        
        
        long ans = 0;
        //Now we subtract the count of minimum occurrences from the count of maximum occurrences
        
        for (int i = 0; i< nums.length; i++){
            ans+=((lesserLeft[i]*lesserRight[i]) - (greaterLeft[i]*greaterRight[i]))*nums[i];
        }
        return ans;
    }
}

Shipment Imbalance Solution

SOLUTION

Amazon OA 2023 Questions with Solution

Leave a Comment Cancel reply