970. Meet in the Middle Value
A row of lamps has brightness levels stored in nums (levels may be negative or zero). In one move you may raise or lower the brightness of a single lamp by exactly 1. You want every lamp to end at the same brightness, and the shared level can be any integer, not necessarily one that appears in the row.
Return the minimum number of moves required to make all brightness levels equal. A row with one lamp, or with all levels already equal, needs 0 moves.
Example 1
- Input:
- nums = [4,9,2]
- Output:
- 7
- Explanation:
Meeting at 4 costs 0 + 5 + 2 = 7, and no other common value does better.
Example 2
- Input:
- nums = [-3,-3,-3]
- Output:
- 0
- Explanation:
All values are already equal, so no moves are needed.
Example 3
- Input:
- nums = [1,100,2,99]
- Output:
- 196
- Explanation:
Any common value between 2 and 99 costs 99 + 97 = 196 moves, the minimum possible.
Constraints
- 1 ≤ nums.length ≤ 105
- -104 ≤ nums[i] ≤ 104
- The answer is at most 109, so it fits in a 32-bit signed integer
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)