We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This one was a bit frustrating for me. It took me some time to understand what I am supposed to do. Maybe the following explanation will help someone.
So we have an array arr of size n. We need to select from arr a subarray of size k (that is less or equal to n) and find unfairness for this subarray. You can picture this subarray as a window (this comparison really helped me). We start from the arr[0] and keep moving our selection/window of k elements to the right until its last element is equal to arr last element. For every iteration we calculate unfairness. To minimize unfairness and simplify calculation for every subarray, we need to sort arr.
Let's say that our sorted arr is [1, 2, 3, 4, 5, 6] and k is 3.
So for the first iteration we select subarray {1, 2, 3}: [{1, 2, 3}, 4, 5, 6]. Because arr is sorted, the first element in the subarray is the smallest and the last element is the largest, so we can easily calculate unfairness: 3-1=2. Then we move our window by one and repeat all the operations. When unfairness for every subarray is found, we just need to find the smallest one and return it (you can optimize your solution and check min unfairness for every iteration).
Max Min
You are viewing a single comment's thread. Return to all comments →
This one was a bit frustrating for me. It took me some time to understand what I am supposed to do. Maybe the following explanation will help someone.
So we have an array arr of size n. We need to select from arr a subarray of size k (that is less or equal to n) and find unfairness for this subarray. You can picture this subarray as a window (this comparison really helped me). We start from the arr[0] and keep moving our selection/window of k elements to the right until its last element is equal to arr last element. For every iteration we calculate unfairness. To minimize unfairness and simplify calculation for every subarray, we need to sort arr.
Let's say that our sorted arr is [1, 2, 3, 4, 5, 6] and k is 3. So for the first iteration we select subarray {1, 2, 3}: [{1, 2, 3}, 4, 5, 6]. Because arr is sorted, the first element in the subarray is the smallest and the last element is the largest, so we can easily calculate unfairness: 3-1=2. Then we move our window by one and repeat all the operations. When unfairness for every subarray is found, we just need to find the smallest one and return it (you can optimize your solution and check min unfairness for every iteration).
How all this looks like: