2659. Make Array Empty

Description

You are given an integer array nums containing distinct numbers, and you can perform the following operations until the array is empty:

• If the first element has the smallest value, remove it
• Otherwise, put the first element at the end of the array.

Return an integer denoting the number of operations it takes to make nums empty.

 

Example 1:

Input: nums = [3,4,-1]
Output: 5

Operation	Array
1	[4, -1, 3]
2	[-1, 3, 4]
3	[3, 4]
4	[4]
5	[]

Example 2:

Input: nums = [1,2,4,3]
Output: 5

Operation	Array
1	[2, 4, 3]
2	[4, 3]
3	[3, 4]
4	[4]
5	[]

Example 3:

Input: nums = [1,2,3]
Output: 3

Operation	Array
1	[2, 3]
2	[3]
3	[]

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• All values in nums are distinct.

 

Solutions

Solution: Hash Table

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const countOperationsToEmptyArray = function (nums) {
  const n = nums.length;
  const numMap = new Map();
  let result = n;

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    numMap.set(num, index);
  }

  nums.sort((a, b) => a - b);

  for (let index = 1; index < n; index++) {
    const prev = nums[index - 1];
    const current = nums[index];

    if (numMap.get(current) < numMap.get(prev)) {
      result += n - index;
    }
  }

  return result;
};