Contents
Min Steps to Make Piles Equal Height Solution
Alexa is given n piles of equal or unequal heights. In one step, Alexa can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height.
Example 1:
Input: piles = [5, 2, 1]
Output: 3
Explanation:
Step 1: reducing 5 -> 2 [2, 2, 1]
Step 2: reducing 2 -> 1 [2, 1, 1]
Step 3: reducing 2 -> 1 [1, 1, 1]
So final number of steps required is 3.
Also See: Amazon OA Online Assessment 2023 Questions and Answers
SOLUTION
Program: Min Steps to Make Piles Equal Height Solution in Python
Let’s take an example:
Input : [1, 1, 2, 2, 2, 3, 3, 3, 4, 4]
Output : 15
After sorting in reverse, we have…
[4, 4, 3, 3, 3, 2, 2, 2, 1] –> (2 steps to transform the 4’s) –> The 3’s must wait for 2 numbers before it to finish their reduction
[3, 3, 3, 3, 3, 2, 2, 2, 1] –> (5 steps to transform the 3’s) –> The 2’s must wait for 5 numbers before it to finish their reduction
[2, 2, 2, 2, 2, 2, 2, 2, 1] –> (8 steps to transform the 2’s) –> The 1’s must wait for 8 numbers before it to finish their reduction
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
- Why did we sort in reverse? Because we want to process the maximum / largest number(s) first, which is what the question wants. At each step, we can only reduce the largest number(s) to the value of the 2nd-largest number(s)
- The main idea throughout the algorithm is that – Every time I meet a different number in the reverse-sorted array, I have to count how many numbers came before it. This represents the number of steps that was taken to reduce these numbers to the current number
from typing import List
def min_steps_balance(piles: List[int]) -> int:
"""
Time : O(N log N)
Space : O(1), where N = len(s)
"""
# EDGE CASE
if len(piles) < 2:
return 0
# SORT THE BLOCKS
piles = sorted(piles, reverse=True)
# COUNT THE STEPS WE NEED
steps = 0
# EACH TIME WE SEE A DIFFERENT ELEMENT, WE NEED TO SEE HOW MANY ELEMENTS ARE BEFORE IT
for i in range(1, len(piles)):
steps += i if piles[i - 1] != piles[i] else 0
return steps
if __name__ == "__main__":
print(min_steps_balance([50]) == 0)
print(min_steps_balance([10, 10]) == 0)
print(min_steps_balance([5, 2, 1]) == 3)
print(min_steps_balance([4, 2, 1]) == 3)
print(min_steps_balance([4, 5, 5, 4, 2]) == 6)
print(min_steps_balance([4, 8, 16, 32]) == 6)
print(min_steps_balance([4, 8, 8]) == 2)
print(min_steps_balance([4, 4, 8, 8]) == 2)
print(min_steps_balance([1, 2, 2, 3, 3, 4]) == 9)
print(min_steps_balance([1, 1, 2, 2, 2, 3, 3, 3, 4, 4]) == 15)
Min Steps to Make Piles Equal Height Python Easiest Solution
from collections import Counter
def minStepEqualPiles(A):
cnt = Counter(A)
nums = sorted(cnt.keys(), reverse=True)
k, ans = 0, 0
for x in nums[:-1]:
k += cnt[x]
ans += k
return ans
A = [5, 2, 1]
print(minStepEqualPiles(A))
A = [4, 5, 5, 4, 2]
print(minStepEqualPiles(A))
Program: Min Steps to Make Piles Equal Height Solution in Java
For piles = [5, 2, 1], 5 needs 2 steps to come to 1(5 -> 2 -> 1) and 2 needs 1 step to 1(2 -> 1) and 1 for 0 step. We just need to sort the array and record how many different numbers appeared before and sum them up.
public class Main {
public int minSteps(int[] piles){
int len = piles.length;
if(len <= 1) return 0;
Arrays.sort(piles);
int res = 0, distinctNums = 0;
for(int i = 1; i < len; ++i){
if(piles[i] == piles[i - 1]){
res += distinctNums;
}
else{
++distinctNums;
res += distinctNums;
}
}
return res;
}
public static void main(String[] args) {
int[][] testcases = {{5, 2, 1}, {4,5,5,4,2}};
for(int[] testcase: testcases)
System.out.println(new Main().minSteps(testcase));
}
}
Program: Min Steps to Make Piles Equal Height Solution in C++
Lets visualize the piles, lets use A instead of boxes
5: AAAAA
2: AA
1: A
On the first step we cut 5: AAAAA to 2: AA
2: AA
2: AA
1: A
On the second step we cut first strings of 2: AA to 1: A
1: A
1: AA
1: A
On the third step we cut first strings of 2: AA to 1: A
1: A
1: A
1: A
If we will have two piles with the same length, for example:
5: AAAAA
5: AAAAA
1: A
On the first step we cut first 5: AAAAA to 1: A:
1: A
5: AAAAA
1: A
On the second step we cut second 5: AAAAA to 1: A:
1: A
1: A
1: A
In other words in order to determine the minimum number of steps required to make all of the piles equal in height we need to sort the array and count how many piles with different height exists and sum them up.
The C++ code:
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <set>
#include <iterator>
#include <unordered_map>
using namespace std;
/*
int solution(const vector<int> & v) {
priority_queue<int> pq(v.begin(), v.end());
int tallest_num = 0;
int steps = 0;
while ( ! pq.empty()) {
int tallest = pq.top(); pq.pop();
if (pq.empty()) { return steps; }
if (tallest == pq.top()) {
++ tallest_num;
}
else {
steps += tallest_num;
}
}
return steps;
}
*/
int solution3(const vector<int> & v) {
int v_size = v.size();
int result = 0;
int min_num = *std::min_element(v.begin(), v.end());
std::unordered_map<int, int> um;
for(auto i : v) {
++ um[i];
}
for(auto i: um) {
result += i.second;
}
return result;
}
int solution2(vector<int> v) {
int v_size = v.size();
int result = 0;
unordered_set<int> us(v.begin(), v.end());
unordered_multiset<int> ums(v.begin(), v.end());
for(auto i : us) {
result += ums.count(i);
}
return result;
}
int solution(vector<int> v) {
int v_size = v.size();
if(v_size < 2) { return 0; }
std::sort(v.begin(), v.end());
// std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
int sum = 0;
for (int i = 1; i < v_size; ++i) {
if (v[v_size - i - 1] != v[v_size - i]) {
sum += i;
}
}
return sum;
}
int main() {
cout << solution({5,2,1}) << " Expected: 3" << endl;
cout << solution({5,5,2,2,1,1}) << " Expected: 6" << endl;
cout << solution({5,5,1}) << " Expected: 2" << endl;
cout << solution({5,5,5,5,1}) << " Expected: 4" << endl;
cout << solution({3,2,2}) << " Expected: 1" << endl;
return 0;
}
Complexity of this solution is O(N* Log(N)) where N is length of the string but I believe there is a solution with linear complexity I just can’t process well all corner cases.
Microsoft Online Assessment 2023 Questions List
- Maximal Network Rank Solution
- Min Deletions To Obtain String in Right Format
- Day of week that is K days later Solution
- Minimum Adjacent Swaps to Make Palindrome Solution
- Lexicographically Smallest String
- Longest Substring Without Two Contiguous Occurrences of Letter
- String Without 3 Identical Consecutive Letters
- Microsoft OA Longest Semi-Alternating Substring
- Microsoft OA Min Steps to Make Piles Equal Height
- Max Inserts to Obtain String Without 3 Consecutive ‘a’
- Concatenated String Length with unique Characters
- Largest K such that both K and -K exist in array
- Microsoft OA Min Adj Swaps to Group Red Balls
- Maximum Length of a Concatenated String with Unique Characters
- Microsoft OA Unique Integers That Sum Up To 0
- Find N Unique Integers Sum up to Zero
- Microsoft OA Particle Velocity Solution
- Microsoft OA Arithmetic Slices Solution
- Microsoft OA Widest Path Without Trees Solution
- Microsoft OA Jump Game Solution
- Microsoft OA Fair Indexes Solution
Its java code ran but c++ was not working in an online test when compiled
It was a typo mistake actually it was javascript code not C++, but we have also included C++ solution for it with explanation for better understanding.