Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
4.
Algorithm
5.
Working
6.
Explanation
7.
Implementation
7.1.
Approach 1(C++)
7.1.1.
Code
7.1.2.
Output
7.2.
Approach 2(Python 3)
7.2.1.
Code
7.2.2.
Output
7.3.
Approach 3(C#)
7.3.1.
Code
7.3.2.
Output
8.
Complexity Analysis
8.1.
Time complexity
8.2.
Space complexity
9.
Frequently Asked Questions
9.1.
What does it mean when an array is referred to as a data structure?
9.2.
Is it possible to modify the size of an array during execution?
9.3.
What are some of the uses of arrays?
10.
Conclusion
Last Updated: Mar 27, 2024
Easy

Rearrange array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i

Introduction

There's no denying that cracking programming job interviews is challenging, and it's even more difficult if you want to crack Coding interviews at tech firms like Google, Microsoft, or Amazon.

                                                             

                                                                                 Source

However, you can still succeed by carefully planning and preparing the necessary topics.

This blog will discuss one of the widespread array-based Programming Interview Questions to increase your coding knowledge. We will discuss the method with which we can rearrange an array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i.

Without further ado, let’s start.

                                                      

                                                                           Source

Problem Statement

An integer array containing odd and even integer values is given to us. The goal is to rearrange an array so that arr[i] is greater than or equal to arr[j], based on the condition that the value at index arr[i] is even and if the value at arr[i] is odd, arr[i] is less than equal to arr[j].

We have to arrange the array so that elements in even locations are more significant than all preceding elements, while ones in odd positions are smaller.

Let's look at some input/output possibilities for this.

Input array: 

arr[] = {5, 10, 15, 20, 25, 30, 35}

Output array:

New array after rearrangement of elements = {  20, 25, 15, 30, 10, 35, 5 }
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Here is an example of understanding the problem of rearranging an array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i.

Input array: int arr[] =  { 4, 5, 1, 2, 9, 8 }

Output: After rearranging the elements of the array: { 4, 5, 2, 8, 1, 9 }

Explanation: We're given an array of odd and even integers to work with. Now we'll compare the arr[i] position to the arr[j] position and see if arr[i] is even or odd. If arr[i] is even, make sure arr[i] is more than arr[j], and if arr[i] is odd, make sure arr[i] is less than arr[j].

Algorithm

The algorithm for rearranging the elements of the array is as follows:

  • Set the even positions to the floor of ( n/2).
  • Set the odd places to n - even positions.
  • Create a temporary array.
  • Copy all the elements of the given array to the temporary array.
  • The temporary array should be sorted.
  • Set the value of j equals to odd positions - 1.
  • Copy the value of the temporary array to the original array[j] at the even position(index-based) of the given array and decrement the value of j by 1.
  • Set the value of j equals to odd positions.
  • Copy the value of the temporary array to the original array[j] at the odd position(index-based) of the given array and increment the value of j by 1.
  • Print the elements of the original array.

Working

We will see the working of the algorithm. We are not using index-based numbering in this case. Elements in the 0 position should be treated as if they were in the first position, which is unusual. We count from 1  as odd to n numbers.

Make a copy of the given initial array into the temporary array, and then count how many even and odd positions can be found in the array. After that, we'll sort the array in ascending order.

Update the array elements at the odd position (non-array-based indexing) as decreasing values of odd place – 1 to 0 from the temporary array.

The elements from half of the temporary array will be stored in the original array's odd position. Similarly, the rest of the values from the second half of the temporary array will be put at the even part of the original array. It will allow us to rearrange the array so that elements in even places are larger and elements in odd positions are smaller than all of the elements before them.

Explanation

Here is the diagrammatic explanation of the working of the algorithm to better understand the solution.

Step 1: Original array;

Even Positions: floor ( n/2 ) => floor ( 7 /2 ) = 3.

Odd Positions: n - even Positions =>( 7 - 3)= 4.

 

Step  2: Temporary Array Elements; We will copy all the original array elements to the temporary array and sort the elements.

 

Step 3: Set j equals to odd positions - 1. Copy the temporary array elements to the original array[j] at the even place (index-based) of the given array and decrement the value of j by 1.

The updated original array;

We can see that the elements only at the even positions have been changed, and the rest elements are unchanged.

 

Step 4: Now set j equals to odd positions. Copy the value of the temporary array to the original array[j] at the odd position(index-based) of the given array and increment the value of j by 1.

The new original array;

This is the required and updated array. Print this array as output.

Now we are ready to see the algorithm’s implementation. Let’s understand the implementation of this algorithm in different ways.

                                                    

                                                                                                  Source

Implementation

Here is the implementation of the algorithm in different programming languages.

Approach 1(C++)

The given code is the implementation of our algorithm in C++ language.

Code

#include<iostream>
#include<algorithm>
using namespace std;
void rearrangeArray(int array[], int n)
{
    int evenPosition = n / 2;
    int oddPosition = n - evenPosition;
    int temporaryArray[n];
    for (int i = 0; i < n; i++)
        temporaryArray[i] = array[i];
    sort(temporaryArray, temporaryArray + n);
    int j = oddPosition - 1;
    for (int i = 0; i < n; i += 2)
    {
        array[i] = temporaryArray[j];
        j--;
    }
    j = oddPosition;
    for (int i = 1; i < n; i += 2)
    {
        array[i] = temporaryArray[j];
        j++;
    }
}
void printArray(int array[], int n)
{
    for (int i = 0; i < n; i++)
        cout << array[i] << " ";
}

int main()
{
    int array[] = { 1,4,6,2,4,8,9};
    int n = sizeof(array) / sizeof(array[0]);
    rearrangeArray(array, n);
    printArray(array,n);
    return 0;
}

Output

Approach 2(Python 3)

The given code is the implementation of our algorithm in Python language.

Code

import array as a 
import numpy as np 

# function to rearrange the given array 
def rearrangeArray(arr, n): 

    # total number of even positions 
    evenPos = int(n / 2) 
    
    # total number of odd positions 
    oddPos = n - evenPos 
    
    # intialising empty array
    tempArray = np.empty(n, dtype = object) 
    
    # copy original array temporary array 
    for i in range(0, n): 
        tempArray[i] = arr[i] 
        
    # sort the temporary array 
    tempArray.sort() 
    j = oddPos - 1
    
    # filling up  the odd position in original array 
    for i in range(0, n, 2): 
        arr[i] = tempArray[j] 
        j = j - 1
    j = oddPos 
    
    # filling up even positions in original array 
    for i in range(1, n, 2): 
        arr[i] = tempArray[j] 
        j = j + 1   
        
    #  Display 
    for i in range(0, n): 
        print (arr[i], end = ' ') 
        
# Driver code 
arr = a.array('i', [ 1, 4, 6, 2, 4, 8, 9 ]) 
rearrangeArray(arr, 7) 

Output

Approach 3(C#)

The given code implements our algorithm using the C# language.

Code

using System; 
  
public class CodingNinjas { 
      
    // Function to rearrange array 
    public static void rearrangeArray(int []array, int n) 
    { 
        // total number of even positions 
        int evenPos = n / 2; 
  
        // total number of odd positions 
        int oddPos = n - evenPos; 
  
        int[] tempArray = new int [n]; 
  
        // copy original array in temporary
        for (int i = 0; i < n; i++) 
            tempArray[i] = array[i]; 
  
        // sorting the temp array 
        Array.Sort(tempArray); 
  
        int j = oddPos - 1; 
  
        // Fill up odd position in array 
        for (int i = 0; i < n; i += 2) { 
            array[i] = tempArray[j]; 
            j--; 
        } 
  
        j = oddPos; 
  
        // Fill up even positions
        for (int i = 1; i < n; i += 2) { 
            array[i] = tempArray[j]; 
            j++; 
        } 
  
        // display
        for (int i = 0; i < n; i++) 
            Console.Write(array[i] + " "); 
    } 
      
    // Driver Code  
    public static void Main() 
    { 
        int[] array = new int []{ 1, 4, 6, 2, 4, 8, 9 }; 
        int size = 7; 
        rearrangeArray(array, size); 
    } 
} 

Output

Also see, Morris Traversal for Inorder and  Rabin Karp Algorithm

 

Complexity Analysis

We have discussed various approaches in different languages of our Algorithm. Now let’s analyse the space and time complexity of the algorithm.

Time complexity

The algorithm's time complexity is O(n log n), where "n" is the number of elements in the array.

Space complexity

The algorithm's time complexity is O(n), where "n" is the number of elements in the array.

Check out this problem - Next Smaller Element

Frequently Asked Questions

What does it mean when an array is referred to as a data structure?

Because they hold elements of the same type, arrays are categorised as homogeneous data structures. Numbers, strings, a boolean value, characters, objects, and other data can be stored. However, after deciding what kind of values your array will hold, all of its elements must be of that type.

Is it possible to modify the size of an array during execution?

No, we won't be able to adjust the array size. There are, however, similar data types that allow for size changes.

What are some of the uses of arrays?

Other data structures, such as linked lists, are implemented using them. Arrays are commonly used to represent database records. The computer uses it in lookup tables. It effectively implements memory addressing logic, in which indices serve as addresses for a one-dimensional array of memory.

Conclusion

This blog discussed the method with which we can rearrange an array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i.

We have discussed,

  • Example of the method.
  • Algorithm for the solution using the index-based method.
  • Working of the Algorithm.
  • Explanation of the Algorithm.
  • Implementation of the Algorithm.

This blog is related to array rearrangement, so it is advised to check these articles on rearranging an array and rearranging an array such that arr[i] = i. You can visit Coding Ninjas Studio for more Coding Interview Questions.

Recommended Problems -

 

To learn more about array rearrangement problems, visit the Array rearranging Problems at Coding Ninjas Studio.

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, interview bundle, follow guided paths for placement preparations, and much more!!

We wish you Good Luck! Keep coding and keep reading Ninja!!

Live masterclass