Problem 8: Wave Array Problem

Software Development
#1

Wave Array

Problem Description

Given an array of integers A, sort the array into a wave like array and return it, In other words, arrange the elements into a sequence such that

a1 >= a2 <= a3 >= a4 <= a5…

NOTE : If there are multiple answers possible, return the one that’s lexicographically smallest.

Problem Constraints

1 <= len(A) <= 106
1 <= A[i] <= 106

Input Format

First argument is an integer array A.

Output Format

Return an array arranged in the sequence as described.

Example Input

Input 1:

A = [1, 2, 3, 4]

Input 2:

A = [1, 2]

Example Output

Output 1:

[2, 1, 4, 3]

Output 2:

[2, 1]

Example Explanation

Explanation 1:

One possible answer : [2, 1, 4, 3] Another possible answer : [4, 1, 3, 2] First answer is lexicographically smallest. So, return [2, 1, 4, 3].

Explanation 1:

Only possible answer is [2, 1].

  1. All submissions are automatically checked for plagiarism, and flagged solutions might not be counted towards the total score.
  2. Do not hesitate to discuss the solution with your batchmates, or take help from your Coach to build intuition.
  3. DO NOT move on from a problem until you have understood the approach very well.
  4. Plagiarism would defeat the purpose of learning a new pattern and concept.
#2

Solution: Wave Array
Example Explanation
Example Input

Input 1:

A = [1, 2, 3, 4]

Input 2:

A = [1, 2]

Example Output

Output 1:

[2, 1, 4, 3]

Output 2:

[2, 1]

Explanation 1:

One possible answer : [2, 1, 4, 3] Another possible answer : [4, 1, 3, 2] First answer is lexicographically smallest. So, return [2, 1, 4, 3].

Explanation 1:

Only possible answer is [2, 1].


import java.util.Collections;
public class Solution {
    public ArrayList<Integer> wave(ArrayList<Integer> A) {
        // A = [1, 2, 3, 4, 5] ==> [2, 1, 4, 3, 5]
        Collections.sort(A);
        for (int idx = 0; idx < A.size() - 1; idx += 2 ) {
            // Swap ith and i +1th element without using a third variable
            A.set( idx, A.get(idx) + A.get(idx + 1) );
            A.set( idx + 1, A.get(idx) - A.get(idx + 1) );
            A.set( idx, A.get(idx) - A.get(idx + 1) );
        }
        return A;
        
    }
}