Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Removing Minimum and Maximum From Array

Problem Statement

Determine the minimum number of deletions required to remove the smallest and the largest elements from an array of integers.

In each deletion, you are allowed to remove either the first (leftmost) or the last (rightmost) element of the array.

Examples

  1. Example 1:

    • Input: [3, 2, 5, 1, 4]
    • Expected Output: 3
    • Justification: The smallest element is 1 and the largest is 5. Removing 4, 1, and then 5 (or 5, 4, and then 1) in three moves is the most efficient strategy.

  2. Example 2:

    • Input: [7, 5, 6, 8, 1]

.....

.....

.....

Like the course? Get enrolled and start learning!
Pavel Kostenko

Pavel Kostenko

· a year ago

Original solution makes 4 passes:

  • find min element
  • find index of min element
  • find max element
  • find index of max element

these can be combined into a single pass.

class Solution {
  /**
   * Time: O(n) - one pass over each value to find min & max
   * Space: O(1) - variables does not scale with the input size
   * @param nums
   */
  minMoves(nums: number[]) {
    let minIdx = -1;
    let min = Infinity;
    let maxIdx = -1;
    let max = -Infinity;

    for (let i = 0; i < nums.length; i++) { // Time: O(n)
      if (nums[i] < min) {
        min = nums[i];
        minIdx = i;
      }
      if (nums[i] > max) {
        max = nums[i];
        maxIdx = i;
      }
    }
    // removing from both sides
    // (smallest index + 1) => total removals from the left
    /