## Problem You are given an array of integers. In each turn you may swap any one pair of adjacent elements. Return the minimum number of turns (swaps) needed to sort the array in non-decreasing order. ```python def minimum_turns(arr: list[int]) -> int: pass ``` ``` Input: arr = [3, 1, 2] Output: 2 # [3,1,2] -> [1,3,2] -> [1,2,3] (2 swaps) Input: arr = [4, 3, 2, 1] Output: 6 # Reverse of 4 elements = 4*3/2 = 6 inversions Input: arr = [1, 2, 3] Output: 0 ``` ## Follow-ups 1. What is the relationship between minimum adjacent swaps and the number of inversions in the array? 2. How can merge sort be used to count inversions in O(n log n)? 3. If you can swap any two elements (not just adjacent), what is the minimum number of swaps then? 4. How does duplicate handling change the inversion count logic?

InterviewDB Question

Minimum Turns to Sort Array Using Adjacent Swaps

phone

Question Details

Problem You are given an array of integers. In each turn you may swap any one pair of adjacent elements. Return the minimum number of turns (swaps) needed to sort the array in non-decreasing order. Follow-ups What is the relationship between minimum adjacent swaps and the number of inversions in the array? How can merge sort be used to count inversions in O(n log n)? If you can swap any two elements (not just adjacent), what is the minimum number of swaps then? How does duplicate handling change…

Full Details

🔒

Unlock all Ziphq questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a ziphq interview during the phone round.

It covers the following topics: Phone, Sorting, Coding, Arrays, Onsite .

Topics

Phone Sorting Coding Arrays Onsite

Minimum Turns to Sort Array Using Adjacent Swaps

Question Details

Full Details

About This Question

Topics

More Ziphq Interview Questions