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

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.
Example 2:
- Input: [7, 5, 6, 8, 1]

.....

Like the course? Get enrolled and start learning!

Mohammed Dh Abbas

· 2 years ago

class Solution:
    def minMoves(self, nums):
        
        min_number = float('inf')
        max_number = float('-inf')

        max_index = min_index = 0 

        for index, num in enumerate(nums):
            if num < min_number:
                min_number = num
                min_index = index
            if num > max_number:
                max_number = num
                max_index = index

        # left deletes to min and max items
        lef_min_del = min_index + 1
        lef_max_del = max_index + 1

        # right deletes to min an max items 
        right_min_del = len(nums) - min_index 
        right_max_del = len(nums) - max_index 
        
        # deletes that could cover both of min and max items
        lef_both = max(lef_min_del, lef_max_del)

Pavel Kostenko

· 2 years 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
    /

M

mailman14736

· 3 months ago