
:::section{.main}

This article is part of the [Scaler Topics Fortnightly Contest - 13](https://www.scaler.com/topics/contests/437346/)

### Solution Approach

- As the cost is the sum of absolute difference of adjacent elements.
- So, the cost will be minimum if the array is in increasing or decreasing order. Both of them will give minimum cost. And both of the array will be beautiful.
- So, we have to just find the minimum number of swaps required to make array increasing or decreasing.

**Time Complexity** - O(nlogn)  
**Space Complexity** - O(n)

:::

:::section{.main}
## C++ Implementation
```cpp
int Solution::solve(vector < int > & A) {
    int n = A.size();
    assert(n >= 1 and n <= 1e5);
    vector < int > Sorted = A;
    vector < int > RevSorted = A;
    vector < int > tempA = A;
    unordered_map < int, int > mpSorted;
    unordered_map < int, int > mpRevSorted;
    sort(Sorted.begin(), Sorted.end());
    sort(RevSorted.rbegin(), RevSorted.rend());
    for (int i = 0; i < n; i++) {
        assert(A[i] >= 1 and A[i] <= 2e9);
        mpSorted[Sorted[i]] = i;
        mpRevSorted[RevSorted[i]] = i;
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        while (A[i] != Sorted[i]) {
            swap(A[i], A[mpSorted[A[i]]]);
            ans1 += 1;
        }
    }
    for (int i = 0; i < n; i++) {
        while (tempA[i] != RevSorted[i]) {
            swap(tempA[i], tempA[mpRevSorted[tempA[i]]]);
            ans2 += 1;
        }
    }
    return min(ans1, ans2);
}
```
:::

:::section{.main}
## Java Implementation
```java
public class Solution {
    public int solve(int[] A) {
        int n = A.length;
        int[] temp= new int[n];
        int[] s= new int[n];
        int[] r= new int[n];
        for(int i=0;i<n;i++)
        {
            temp[i]=s[i]=r[i]=A[i];
        }
        Arrays.sort(s);
        Arrays.sort(r);
        
        for (int i = 0; i < n / 2; i++) {
            int t = r[i];
            r[i] = r[n - i - 1];
            r[n - i - 1] = t;
        }
    
        HashMap<Integer,Integer> pos=new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> ros=new HashMap<Integer,Integer>();
        for(int i=0;i<A.length;i++)
        {
            pos.put(A[i],i);
            ros.put(A[i],i);
        }
        int ans1=0,ans2=0;
        for(int i=0;i<s.length;i++)
        if(A[i]!=s[i])
        {
            int t=A[i];
            int tmp = A[pos.get(s[i])];
            A[pos.get(s[i])] = A[i];
            A[i] = tmp;
            pos.put(t,pos.get(s[i]));
            ans1++;
        }
        for(int i=0;i<r.length;i++)
        if(temp[i]!=r[i])
        {
            int t = temp[i];
            int tm = temp[ros.get(r[i])];
            temp[ros.get(r[i])] = temp[i];
            temp[i] = tm;
            ros.put(t,ros.get(r[i]));
            ans2++;
        }
        return Math.min(ans1,ans2);
    }
}
```
:::

:::section{.main}
## Python Implementation
```python
class Solution:
    def solve(self, A):
        n = len(A)
        Sorted = [0] * n
        RevSorted = [0] * n
        tempA = [0] * n
        for i in range(n):
            Sorted[i] = A[i]
            RevSorted[i] = A[i]
            tempA[i] = A[i]
        mpSorted = {}
        mpRevSorted = {}
        Sorted.sort()
        RevSorted.sort(reverse=True)
        for i in range(n):
            mpSorted[Sorted[i]] = i
            mpRevSorted[RevSorted[i]] = i
        ans1 = 0
        ans2 = 0
        for i in range(n):
            while A[i] != Sorted[i]:
                val = A[i]
                A[i] = A[mpSorted[A[i]]]
                A[mpSorted[val]] = val
                ans1 += 1
        for i in range(n):
            while tempA[i] != RevSorted[i]:
                val = tempA[i]
                tempA[i] = tempA[mpRevSorted[tempA[i]]]
                tempA[mpRevSorted[val]] = val
                ans2 += 1
        return min(ans1, ans2)
```
:::

Software Engineer and Instructor at Scaler

Jitender Punia

DSA Problem Solving for Interviews using Java

Welcome to the free Python course with certificate for beginners, designed to help you kickstart your programming journey. This comprehensive Python course online offers a certificate upon completion, covering essential topics like basic Python fundamentals, data structures, object-oriented programming, and more. With 9 hours and 48 minutes of content, you'll gain the knowledge and confidence to start working on your Python projects.

Python Course for Beginners With Certification: Mastering the Essentials

Embark on your programming journey with our Free Java Course with Certificate. Master the fundamentals of Java and gain the skills needed for advanced Java development. This easy-to-follow course is designed with beginners in mind, offering a structured learning path to specialize in Java programming. With no prerequisites, this online Java course empowers you to learn Java at your own pace and take the first step toward a promising career in tech.

Software Engineer & Instructor

Java Course - Mastering the Fundamentals

Scaler Topics free DBMS course is designed to help beginners learn about the fundamental concepts of database management systems. The course is completely online, and it comes with a free certificate of completion that you can add to your resume or LinkedIn profile. You'll learn about the most popular DBMS like MySQL, Oracle, and SQL Server, as well as the theoretical foundations of databases.

Lead DSML Instructor at Scaler

DBMS Course - Master the Fundamentals and Advanced Concepts

Kickstart your journey into web development with this free JavaScript course online with a certificate. Designed for beginners, this comprehensive JavaScript online course covers the essential concepts and skills needed to master Javascript, one of the most popular and widely used programming languages in the world. With a course duration of 10 hours and 9 minutes, you'll learn everything from the basics to advanced techniques, all at your own pace.

JavaScript Course With Certification: Unlocking the Power of JavaScript

Gain programming expertise with our C++ Course! Covering basics to advanced concepts, this online program provides a comprehensive curriculum encompassing environment setup, variables, conditional statements, loops, functions, pointers, arrays, sorting, character arrays, strings, and more. This C++ online course is perfect for beginners or seasoned programmers looking to enhance their skills and earn a certificate.

Instructor & Engineering Lead

C++ Course: Learn the Essentials

Introducing the Free Data Science with Python and SQL Certification Course Online, a comprehensive beginner's program designed to help aspiring data scientists learn the essential skills in the rapidly growing field of data science. This course offers a unique blend of practical and theoretical knowledge, combining the powerful programming language Python and the versatile database management system SQL to help you analyze, visualize, and interpret data efficiently.


Python and SQL for Data Science

Scaler Topics shares the solution approach for Fortnightly contest 13 (Make Beautiful Array) in Java, Python, and C++ programming languages.

Solution 2 for Scaler Topics Fortnightly Contest - 13

Team Scaler

---
title: Solution 2 for Scaler Topics Fortnightly Contest - 13
description: Scaler Topics shares the solution approach for Fortnightly contest 13 (Make Beautiful Array) in Java, Python, and C++ programming languages.
author: Team Scaler
category: DSA
---

:::section{.main}

This article is part of the [Scaler Topics Fortnightly Contest - 13](https://www.scaler.com/topics/contests/437346/)

### Solution Approach

- As the cost is the sum of absolute difference of adjacent elements.
- So, the cost will be minimum if the array is in increasing or decreasing order. Both of them will give minimum cost. And both of the array will be beautiful.
- So, we have to just find the minimum number of swaps required to make array increasing or decreasing.

**Time Complexity** - O(nlogn)  
**Space Complexity** - O(n)

:::

:::section{.main}
## C++ Implementation
```cpp
int Solution::solve(vector < int > & A) {
    int n = A.size();
    assert(n >= 1 and n <= 1e5);
    vector < int > Sorted = A;
    vector < int > RevSorted = A;
    vector < int > tempA = A;
    unordered_map < int, int > mpSorted;
    unordered_map < int, int > mpRevSorted;
    sort(Sorted.begin(), Sorted.end());
    sort(RevSorted.rbegin(), RevSorted.rend());
    for (int i = 0; i < n; i++) {
        assert(A[i] >= 1 and A[i] <= 2e9);
        mpSorted[Sorted[i]] = i;
        mpRevSorted[RevSorted[i]] = i;
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        while (A[i] != Sorted[i]) {
            swap(A[i], A[mpSorted[A[i]]]);
            ans1 += 1;
        }
    }
    for (int i = 0; i < n; i++) {
        while (tempA[i] != RevSorted[i]) {
            swap(tempA[i], tempA[mpRevSorted[tempA[i]]]);
            ans2 += 1;
        }
    }
    return min(ans1, ans2);
}
```
:::

:::section{.main}
## Java Implementation
```java
public class Solution {
    public int solve(int[] A) {
        int n = A.length;
        int[] temp= new int[n];
        int[] s= new int[n];
        int[] r= new int[n];
        for(int i=0;i<n;i++)
        {
            temp[i]=s[i]=r[i]=A[i];
        }
        Arrays.sort(s);
        Arrays.sort(r);
        
        for (int i = 0; i < n / 2; i++) {
            int t = r[i];
            r[i] = r[n - i - 1];
            r[n - i - 1] = t;
        }
    
        HashMap<Integer,Integer> pos=new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> ros=new HashMap<Integer,Integer>();
        for(int i=0;i<A.length;i++)
        {
            pos.put(A[i],i);
            ros.put(A[i],i);
        }
        int ans1=0,ans2=0;
        for(int i=0;i<s.length;i++)
        if(A[i]!=s[i])
        {
            int t=A[i];
            int tmp = A[pos.get(s[i])];
            A[pos.get(s[i])] = A[i];
            A[i] = tmp;
            pos.put(t,pos.get(s[i]));
            ans1++;
        }
        for(int i=0;i<r.length;i++)
        if(temp[i]!=r[i])
        {
            int t = temp[i];
            int tm = temp[ros.get(r[i])];
            temp[ros.get(r[i])] = temp[i];
            temp[i] = tm;
            ros.put(t,ros.get(r[i]));
            ans2++;
        }
        return Math.min(ans1,ans2);
    }
}
```
:::

:::section{.main}
## Python Implementation
```python
class Solution:
    def solve(self, A):
        n = len(A)
        Sorted = [0] * n
        RevSorted = [0] * n
        tempA = [0] * n
        for i in range(n):
            Sorted[i] = A[i]
            RevSorted[i] = A[i]
            tempA[i] = A[i]
        mpSorted = {}
        mpRevSorted = {}
        Sorted.sort()
        RevSorted.sort(reverse=True)
        for i in range(n):
            mpSorted[Sorted[i]] = i
            mpRevSorted[RevSorted[i]] = i
        ans1 = 0
        ans2 = 0
        for i in range(n):
            while A[i] != Sorted[i]:
                val = A[i]
                A[i] = A[mpSorted[A[i]]]
                A[mpSorted[val]] = val
                ans1 += 1
        for i in range(n):
            while tempA[i] != RevSorted[i]:
                val = tempA[i]
                tempA[i] = tempA[mpRevSorted[tempA[i]]]
                tempA[mpRevSorted[val]] = val
                ans2 += 1
        return min(ans1, ans2)
```
:::

Learn about Make Beautiful Array Complete Solution.