Out of Place in the Line

Easy

A team is lining up for a group photo, and everyone is supposed to stand in order of height, shortest first (people of the same height may stand in any order among themselves). The array heights shows how they actually lined up: heights[i] is the height of the person at position i. Compare the current line with the correct one (sorted in non-decreasing order) and return the number of positions where the heights differ.

Example 1

heights=[150, 140, 160, 160] → 2

Sorted by height, the line should be [140, 150, 160, 160]. The first two people are out of place.

Example 2

heights=[3, 1, 2] → 3

The right order is [1, 2, 3], and no position matches it.

Example 3

heights=[5, 5, 7] → 0

Constraints

1 ≤ len(heights) ≤ 1000
1 ≤ heights[i] ≤ 300

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Counting Sort Sorting

Similar problems

Strength of the Weaker Partner Easy Sort by a Reference Order Easy How Many Are Smaller Easy Scooters to Chargers Easy An Author's Impact Score Medium

Input

heights=[150, 140, 160, 160]

Expected

Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.