From the solution we know that maxElem will always be the largest element in the array + 1. So any number mod maxElem i.e “num % maxElem” will always be num as num is smaller than maxElem. Considering this, what is the necessity for “% maxElem” in the solution?
Hi Nagarjun!
We are updating the elements and iterating over them at the same time. The elements at maxIdx and minIdx indexes would change and might become greater than the maxElem. That’s why we have to apply the modulus operator in the formula.
You can review this in the slides as well. When we update the second element at index 1, minIdx is at 0 and the element at minIdx is 43 which is greater than maxElem(7).
We can also achieve the same result by placing max numbers in odd places in 1 loop and then placing even numbers in another loop. It can be achieved with 0(1) space complexity and O(n) time complexity.
> public static void maxMin(int[] arr) {
> int n = arr.length;
> int j = n-1;
> if(n == 2){
> swap(arr, arr[0],arr[1]);
> return;
> }
> for(int i=0; i<j; i += 2){
> swap(arr, i, j);
> j--;
> }
> j = n-1;
> for(int i = 1; i < j; i += 2){
> if(arr[i] > arr[j])
> swap(arr, i, j);
> }
> }
>
> private static void swap(int[] arr, int i, int j){
> int temp = arr[i];
> arr[i] = arr[j];
> arr[j] = temp;
> }