1509. Minimum Difference Between Largest and Smallest Value in Three Moves

You are given an integer array nums. In one move, you can choose one element of nums and change it by any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    int heapSolution(vector<int>& nums) { //o(nlog5)
        priority_queue<int, vector<int>, greater<int>> minHeap; //has max value
        priority_queue<int> maxHeap; //has min value
        
        for(int i = 0; i < nums.size(); i++) {
            minHeap.push(nums[i]);
            maxHeap.push(nums[i]);
            if(maxHeap.size() >= 5) maxHeap.pop();
            if(minHeap.size() >= 5) minHeap.pop();
        }
        vector<int> n;
        while(!minHeap.empty()) {
            n.push_back(minHeap.top());
            minHeap.pop();
        }
        while(!maxHeap.empty()) {
            n.push_back(maxHeap.top());
            maxHeap.pop();
        }
        sort(n.begin(), n.end());
        return slidingWindow(n);
    }
    
    int slidingWindow(vector<int>& nums) {
        int res = INT_MAX;
        for(int l = 0, r = nums.size() - 4; l < 4; l++,r++) {
            res = min(res, nums[r] - nums[l]);
        }
        return res;
    }
public:
    int minDifference(vector<int>& nums) {
        if(nums.size() <= 4) return 0; //we can change all values;
        if(nums.size() >= 8) return heapSolution(nums);
        sort(nums.begin(), nums.end()); //o(nlogn)
        return slidingWindow(nums);
    }
};

375. Guess Number Higher or Lower II

We are playing the Guessing Game. The game will work as follows:

1. I pick a number between 1 and n.
2. You guess a number.
3. If you guess the right number, you win the game.
4. If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
5. Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.

Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.

853. Car Fleet

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer array position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed. The faster car will slow down to match the slower car’s speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

Return the number of car fleets that will arrive at the destination.

951. Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

406. Queue Reconstruction by Height

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

524. Longest Word in Dictionary through Deleting

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

247. Strobogrammatic Number II

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

145. Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

144. Binary Tree Preorder Traversal

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

1392. Longest Happy Prefix

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself).

Given a string s, return the longest happy prefix of s. Return an empty string “” if no such prefix exists.