We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make Median of Array Equal to K

Number: 3387

Difficulty: Medium

Paid? No

Companies: IBM

Problem Description

You are given an integer array nums and a non-negative integer k. In one operation, you can increase or decrease any element by 1. Return the minimum number of operations needed to make the median of nums equal to k. The median is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the larger of the two values is taken.

Key Insights

  • Sort the array to easily locate the median.
  • For a sorted array, the median is at index m = n // 2 (0-indexed).
  • If k is greater than the current median, you must increase numbers starting from the median (and to its right) if they are less than k.
  • If k is less than the current median, you must decrease numbers starting from the median (and to its left) if they are greater than k.
  • Only numbers on the appropriate side of the median (including the median itself) need to be adjusted.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) or O(n) depending on the sorting algorithm in use.

Solution

The algorithm first sorts the array to determine the true median (using 0-indexing, the median is at index n // 2). Then, if k is greater than the median, iterate from the median to the end of the array and for any element less than k, add the difference (k - element) to the operations count. If k is less than the median, iterate from the median to the beginning of the array and for any element greater than k, add the difference (element - k) to the operations count. This greedy approach ensures the minimum number of operations since only the necessary adjustments are made directly on the elements that determine the median.

Code Solutions

# Python Solution
class Solution:
    def minOperations(self, nums, k):
        # Sort the array
        nums.sort()
        n = len(nums)
        # Median index; as per problem definition, if even, pick the larger one
        med_index = n // 2
        operations = 0
        # If k is greater than or equal to the median, adjust numbers from median to end if they are less than k
        if nums[med_index] < k:
            for i in range(med_index, n):
                if nums[i] < k:
                    operations += (k - nums[i])
                else:
                    # Because array is sorted, further elements are >= current element;
                    # if they are already >= k, no need to change.
                    break
        # Else if k is less than the median, adjust numbers from median to start if they are greater than k
        elif nums[med_index] > k:
            for i in range(med_index, -1, -1):
                if nums[i] > k:
                    operations += (nums[i] - k)
                else:
                    # Because array is sorted, earlier elements are <= current;
                    # if they are already <= k, no need to change.
                    break
        # If median is already equal to k, no operations are required.
        return operations

# Example usage:
# sol = Solution()
# print(sol.minOperations([2,5,6,8,5], 4))  # Output: 2
← Back to All Questions