3264. Final Array State After K Multiplication Operations I

Given two sorted arrays a[] and b[] and an element k, the task is to find the element that would be at the k^th position of the combined sorted array.

Examples :

Input: a[] = [2, 3, 6, 7, 9], b[] = [1, 4, 8, 10], k = 5
Output: 6
Explanation: The final combined sorted array would be [1, 2, 3, 4, 6, 7, 8, 9, 10]. The 5th element of this array is 6.

Input: a[] = [100, 112, 256, 349, 770], b[] = [72, 86, 113, 119, 265, 445, 892], k = 7
Output: 256
Explanation: Combined sorted array is [72, 86, 100, 112, 113, 119, 256, 265, 349, 445, 770, 892]. The 7th element of this array is 256.

Constraints:

• 1 <= a.size(), b.size() <= 10⁶
• 1 <= k <= a.size() + b.size()
• 0 <= a[i], b[i] < 10⁸

Approach 01:

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        while (k--) {
            int minIndex = 0;
            for (int i = 1; i < nums.size(); ++i) {
                if (nums[i] < nums[minIndex]) {
                    minIndex = i;
                }
            }
            nums[minIndex] *= multiplier;
        }
        return nums;
    }
};

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        
        while(k):
            minValIndex = nums.index(min(nums))  
            print(minValIndex)              
            nums[minValIndex] = nums[minValIndex]*multiplier
            k -= 1
        return nums

Time Complexity

• Finding the Minimum Element:
  • In each iteration, the algorithm scans the array of size \(n\) to find the minimum element, which takes \(O(n)\) time.
  • Since this step is repeated \(k\) times, the total cost for this step is \(O(k \cdot n)\).
• Multiplying the Minimum Element:
  • The multiplication operation for updating the minimum element is \(O(1)\) and occurs \(k\) times.
  • The total cost for this step is \(O(k)\), which is negligible compared to \(O(k \cdot n)\).
• Overall Time Complexity:

  The total time complexity is \(O(k \cdot n)\).

Space Complexity

• Input Array:
  • The algorithm modifies the input array nums in place, requiring no extra space.
• Auxiliary Variables:
  • Uses variables like minIndex, k, and loop counters, which consume \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(1)\), as no additional space is used apart from the input array.

Approach 02:

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // Min-heap
        
        // Initialize the priority queue with initial values and indices
        for (int i = 0; i < nums.size(); ++i) {
            pq.push({nums[i], i});
        }
        
        while (k--) {
            // Get the minimum element and its index
            auto [val, idx] = pq.top();
            pq.pop();
            
            // Update the value and push it back
            val *= multiplier;
            pq.push({val, idx});
        }
        
        // Reconstruct the result array
        for (int i = 0; i < nums.size(); ++i) {
            auto [val, idx] = pq.top();
            pq.pop();
            nums[idx] = val;
        }
        
        return nums;
    }
};

import heapq

class Solution:
    def getFinalState(self, nums, k, multiplier):
        # Min-heap to store (value, index) pairs
        minHeap = [(val, idx) for idx, val in enumerate(nums)]
        heapq.heapify(minHeap)  # Convert the list to a min-heap

        # Perform k updates
        while k > 0:
            # Extract the minimum value and its index
            val, idx = heapq.heappop(minHeap)
            
            # Update the value and push it back into the heap
            val *= multiplier
            heapq.heappush(minHeap, (val, idx))
            k -= 1

        # Reconstruct the result array
        while minHeap:
            val, idx = heapq.heappop(minHeap)
            nums[idx] = val

        return nums

Time Complexity

• Heap Initialization:
  • Building the priority queue (min-heap) requires inserting \(n\) elements, where each insertion takes \(O(\log n)\). This results in \(O(n \log n)\).
• Processing \(k\) Operations:
  • For each of the \(k\) operations:
    • Removing the smallest element (heap pop) takes \(O(\log n)\).
    • Updating and reinserting the element takes \(O(\log n)\).
  • The total cost for \(k\) operations is \(O(k \cdot \log n)\).
• Reconstructing the Array:
  • Extracting all \(n\) elements from the heap takes \(O(n \log n)\).
• Overall Time Complexity:

  The total time complexity is \(O(n \log n + k \cdot \log n)\), which simplifies to \(O((n + k) \cdot \log n)\).

Space Complexity

• Priority Queue:
  • The priority queue stores up to \(n\) elements, consuming \(O(n)\) space.
• Auxiliary Variables:
  • Uses variables for indices, loop counters, and the heap elements, consuming \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the priority queue.