leetcode 68 - Text Justification

https://leetcode.com/problems/text-justification/

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified and no extra space is inserted between words.

Note:

A word is defined as a character sequence consisting of non-space characters only.
Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

Example 1:

Input: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
Output:
[
“This is an”,
“example of text”,
“justification. “
]
Example 2:

Input: words = [“What”,”must”,”be”,”acknowledgment”,”shall”,”be”], maxWidth = 16
Output:
[
“What must be”,
“acknowledgment “,
“shall be “
]
Explanation: Note that the last line is “shall be “ instead of “shall be”, because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.
Example 3:

Input: words = [“Science”,”is”,”what”,”we”,”understand”,”well”,”enough”,”to”,”explain”,”to”,”a”,”computer.”,”Art”,”is”,”everything”,”else”,”we”,”do”], maxWidth = 20
Output:
[
“Science is what we”,
“understand well”,
“enough to explain to”,
“a computer. Art is”,
“everything else we”,
“do “
]

Constraints:

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100
words[i].length <= maxWidth

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int n = words.size();

int i = 0;
vector<string> result;

while (i < n) {
int width = 0;

int j = i;
while (j < n) {
int len = words[j].size() + (j != i);
if (width + len > maxWidth)
break;
width += len;
j++;
}

string line;

/*
First, imagine no justification at all
- one space between words
- append 'remain' spaces at end of each line

Then, think about line justification
- not last line, and
- number of words of line > 1
*/

int remain = maxWidth - width;
int space = 1;
if (j - i != 1 && j != n) {
int c = remain / (j-i-1);
space += c;
remain -= c * (j-i-1);
}

for (int k = i; k < j; k++) {
if (k != i) {
line.append(space, ' ');
if (j != n && remain-- > 0)
line.append(1, ' ');
}

line += words[k];
}

if (remain > 0)
line.append(remain, ' ');

result.push_back(line);
i = j;
}

return result;
}
};

leetcode 1242 - Web Crawler Multithreaded

https://leetcode.com/problems/web-crawler-multithreaded/
https://leetcode.com/problems/web-crawler-multithreaded/discuss/719974/Efficient-C%2B%2B-with-mutex-and-condition-variable-97

Given a URL startUrl and an interface HtmlParser, implement a Multi-threaded web crawler to crawl all links that are under the same hostname as startUrl.

Return all URLs obtained by your web crawler in any order.

Your crawler should:

Start from the page: startUrl
Call HtmlParser.getUrls(url) to get all URLs from a webpage of a given URL.
Do not crawl the same link twice.
Explore only the links that are under the same hostname as startUrl.

As shown in the example URL above, the hostname is example.org. For simplicity’s sake, you may assume all URLs use HTTP protocol without any port specified. For example, the URLs http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while URLs http://example.org/test and http://example.com/abc are not under the same hostname.

The HtmlParser interface is defined as such:

interface HtmlParser {
// Return a list of all urls from a webpage of given url.
// This is a blocking call, that means it will do HTTP request and return when this request is finished.
public List getUrls(String url);
}
Note that getUrls(String url) simulates performing an HTTP request. You can treat it as a blocking function call that waits for an HTTP request to finish. It is guaranteed that getUrls(String url) will return the URLs within 15ms. Single-threaded solutions will exceed the time limit so, can your multi-threaded web crawler do better?

Below are two examples explaining the functionality of the problem. For custom testing purposes, you’ll have three variables urls, edges and startUrl. Notice that you will only have access to startUrl in your code, while urls and edges are not directly accessible to you in code.

Example 1:

Input:
urls = [
http://news.yahoo.com",
http://news.yahoo.com/news",
http://news.yahoo.com/news/topics/",
http://news.google.com",
http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = “http://news.yahoo.com/news/topics/"
Output: [
http://news.yahoo.com",
http://news.yahoo.com/news",
http://news.yahoo.com/news/topics/",
http://news.yahoo.com/us"
]
Example 2:

Input:
urls = [
http://news.yahoo.com",
http://news.yahoo.com/news",
http://news.yahoo.com/news/topics/",
http://news.google.com"
]
edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
startUrl = “http://news.google.com"
Output: [“http://news.google.com"]
Explanation: The startUrl links to all other pages that do not share the same hostname.

Constraints:

1 <= urls.length <= 1000
1 <= urls[i].length <= 300
startUrl is one of the urls.
Hostname label must be from 1 to 63 characters long, including the dots, may contain only the ASCII letters from ‘a’ to ‘z’, digits from ‘0’ to ‘9’ and the hyphen-minus character (‘-‘).
The hostname may not start or end with the hyphen-minus character (‘-‘).
See: https://en.wikipedia.org/wiki/Hostname#Restrictions_on_valid_hostnames
You may assume there’re no duplicates in the URL library.

Follow up:

Assume we have 10,000 nodes and 1 billion URLs to crawl. We will deploy the same software onto each node. The software can know about all the nodes. We have to minimize communication between machines and make sure each node does equal amount of work. How would your web crawler design change?
What if one node fails or does not work?
How do you know when the crawler is done?

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* // This is the HtmlParser's API interface.
* // You should not implement it, or speculate about its implementation
* class HtmlParser {
* public:
* vector<string> getUrls(string url);
* };
*/
class Solution {
public:
vector<string> crawl(string startUrl, HtmlParser htmlParser) {
int num_threads = thread::hardware_concurrency();

done = false;
working = 0;

host = getHost(startUrl);

q.push(startUrl);
seen.insert(startUrl);

for (int i = 0; i < num_threads; i++)
threads.emplace_back(&Solution::worker, this, &htmlParser);

for (auto &t : threads)
t.join();

return results;
}

private:
string getHost(string &url) {
int i = url.find_first_of("//");
int j = url.find_first_of("/", i+2);

if (j == string::npos)
return url.substr(i+2);
else
return url.substr(i+2, j - i - 2);
}

void worker(HtmlParser *htmlParser) {
while (true) {
unique_lock<mutex> lock(mtx);

cv.wait(lock, [&](){
return q.size() > 0 || done;
});

if (done)
return;

working++;
string url = q.front(); q.pop();
results.push_back(url);

lock.unlock();
vector<string> urls = htmlParser->getUrls(url);
lock.lock();

for (auto &u : urls) {
if (seen.count(u) || getHost(u) != host) continue;

q.push(u);
seen.insert(u);
}

working--;
if (working == 0 && q.empty())
done = true;

cv.notify_all();
}
}

private:
string host;
vector<thread> threads;
mutex mtx;
condition_variable cv;
queue<string> q;
unordered_set<string> seen;
bool done;
int working;
vector<string> results;
};

leetcode 1710 - Maximum Units on a Truck

https://leetcode.com/problems/maximum-units-on-a-truck/

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:

numberOfBoxesi is the number of boxes of type i.
numberOfUnitsPerBoxi is the number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:

  • 1 box of the first type that contains 3 units.
  • 2 boxes of the second type that contain 2 units each.
  • 3 boxes of the third type that contain 1 unit each.
    You can take all the boxes of the first and second types, and one box of the third type.
    The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
    Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Constraints:

1 <= boxTypes.length <= 1000
1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
1 <= truckSize <= 106

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
auto cmp = [](vector<int> &box1, vector<int> &box2) {
return box1[1] > box2[1];
};

sort(boxTypes.begin(), boxTypes.end(), cmp);

int units = 0;
int n = boxTypes.size();

for (int i = 0; i < n && truckSize > 0; i++) {
int size = min(truckSize, boxTypes[i][0]);

units += size * boxTypes[i][1];
truckSize -= size;
}

return units;
}
};

leetcode 1152 - Analyze User Website Visit Pattern

https://leetcode.com/problems/analyze-user-website-visit-pattern/
https://leetcode.com/problems/analyze-user-website-visit-pattern/discuss/357252/C%2B%2B-maps-and-sets

You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct).

For example, [“home”, “away”, “love”], [“leetcode”, “love”, “leetcode”], and [“luffy”, “luffy”, “luffy”] are all patterns.
The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

For example, if the pattern is [“home”, “away”, “love”], the score is the number of users x such that x visited “home” then visited “away” and visited “love” after that.
Similarly, if the pattern is [“leetcode”, “love”, “leetcode”], the score is the number of users x such that x visited “leetcode” then visited “love” and visited “leetcode” one more time after that.
Also, if the pattern is [“luffy”, “luffy”, “luffy”], the score is the number of users x such that x visited “luffy” three different times at different timestamps.
Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

Example 1:

Input: username = [“joe”,”joe”,”joe”,”james”,”james”,”james”,”james”,”mary”,”mary”,”mary”], timestamp = [1,2,3,4,5,6,7,8,9,10], website = [“home”,”about”,”career”,”home”,”cart”,”maps”,”home”,”home”,”about”,”career”]
Output: [“home”,”about”,”career”]
Explanation: The tuples in this example are:
[“joe”,”home”,1],[“joe”,”about”,2],[“joe”,”career”,3],[“james”,”home”,4],[“james”,”cart”,5],[“james”,”maps”,6],[“james”,”home”,7],[“mary”,”home”,8],[“mary”,”about”,9], and [“mary”,”career”,10].
The pattern (“home”, “about”, “career”) has score 2 (joe and mary).
The pattern (“home”, “cart”, “maps”) has score 1 (james).
The pattern (“home”, “cart”, “home”) has score 1 (james).
The pattern (“home”, “maps”, “home”) has score 1 (james).
The pattern (“cart”, “maps”, “home”) has score 1 (james).
The pattern (“home”, “home”, “home”) has score 0 (no user visited home 3 times).
Example 2:

Input: username = [“ua”,”ua”,”ua”,”ub”,”ub”,”ub”], timestamp = [1,2,3,4,5,6], website = [“a”,”b”,”a”,”a”,”b”,”c”]
Output: [“a”,”b”,”a”]

Constraints:

3 <= username.length <= 50
1 <= username[i].length <= 10
timestamp.length == username.length
1 <= timestamp[i] <= 109
website.length == username.length
1 <= website[i].length <= 10
username[i] and website[i] consist of lowercase English letters.
It is guaranteed that there is at least one user who visited at least three websites.
All the tuples [username[i], timestamp[i], website[i]] are unique.

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
40
41
42
43
44
45
class Solution {
public:
vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp,
vector<string>& website) {
unordered_map<string, map<int, string>> m;
unordered_map<string, int> count;

int n = username.size();

for (int i = 0; i < n; i++)
m[username[i]][timestamp[i]] = website[i];

for (auto &ts_map : m) {
unordered_set<string> s;

for (auto it1 = ts_map.second.begin(); it1 != ts_map.second.end(); it1++) {
for (auto it2 = next(it1); it2 != ts_map.second.end(); it2++) {
for (auto it3 = next(it2); it3 != ts_map.second.end(); it3++) {
string pattern = it1->second + "@" + it2->second + "#" + it3->second;

if (s.count(pattern) == 0) {
count[pattern]++;
s.insert(pattern);
}
}
}
}
}

string pattern;
int freq = 0;

for (auto &cnt : count) {
if (cnt.second > freq || (cnt.second == freq && cnt.first < pattern)) {
pattern = cnt.first;
freq = cnt.second;
}
}

int i = pattern.find("@");
int j = pattern.find("#");

return {pattern.substr(0, i), pattern.substr(i+1, j-i-1), pattern.substr(j+1)};
}
};

leetcode 937 - Reorder Data in Log Files

https://leetcode.com/problems/reorder-data-in-log-files/

You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

Letter-logs: All words (except the identifier) consist of lowercase English letters.
Digit-logs: All words (except the identifier) consist of digits.
Reorder these logs so that:

The letter-logs come before all digit-logs.
The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
The digit-logs maintain their relative ordering.
Return the final order of the logs.

Example 1:

Input: logs = [“dig1 8 1 5 1”,”let1 art can”,”dig2 3 6”,”let2 own kit dig”,”let3 art zero”]
Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]
Explanation:
The letter-log contents are all different, so their ordering is “art can”, “art zero”, “own kit dig”.
The digit-logs have a relative order of “dig1 8 1 5 1”, “dig2 3 6”.
Example 2:

Input: logs = [“a1 9 2 3 1”,”g1 act car”,”zo4 4 7”,”ab1 off key dog”,”a8 act zoo”]
Output: [“g1 act car”,”a8 act zoo”,”ab1 off key dog”,”a1 9 2 3 1”,”zo4 4 7”]

Constraints:

1 <= logs.length <= 100
3 <= logs[i].length <= 100
All the tokens of logs[i] are separated by a single space.
logs[i] is guaranteed to have an identifier and at least one word after the identifier.

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
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
bool isLetterLog(string &log) {
int i = log.find_first_of(" ") + 1;

while (i < log.size()) {
if (isdigit(log[i]))
return false;
i++;
}

return true;
}

void sortLetterLogs(vector<string>& logs) {
auto mycmp = [](string &log1, string &log2) {
int i = 0, j = 0;

i = log1.find_first_of(" ");
j = log2.find_first_of(" ");

string sub1 = log1.substr(i);
string sub2 = log2.substr(j);

if (sub1 == sub2)
return log1 < log2;
else
return sub1 < sub2;
};

sort(logs.begin(), logs.end(), mycmp);
}

vector<string> reorderLogFiles(vector<string>& logs) {
vector<string> letterLogs, digitLogs;

for (auto &log : logs) {
if (isLetterLog(log))
letterLogs.push_back(log);
else
digitLogs.push_back(log);
}

sortLetterLogs(letterLogs);

vector<string> result = letterLogs;
result.insert(result.end(), digitLogs.begin(), digitLogs.end());

return result;
}
};

leetcode 792 - Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.

Example 1:

Input: s = “abcde”, words = [“a”,”bb”,”acd”,”ace”]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: “a”, “acd”, “ace”.
Example 2:

Input: s = “dsahjpjauf”, words = [“ahjpjau”,”ja”,”ahbwzgqnuk”,”tnmlanowax”]
Output: 2

Constraints:

1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
s and words[i] consist of only lowercase English letters.

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
class Solution {
public:
bool isSubseq(vector<vector<int>> &indexes, string &word) {
int start = -1;

for (char c : word) {
auto it = upper_bound(indexes[c].begin(), indexes[c].end(), start);
if (it == indexes[c].end())
return false;

start = *it;
}

return true;
}

int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> indexes(256);

int n = s.size();
for (int i = 0; i < n; i++)
indexes[s[i]].push_back(i);

int ans = 0;

for (auto &word : words) {
if (isSubseq(indexes, word))
ans++;
}

return ans;
}
};

leetcode 735 - Asteroid Collision

https://leetcode.com/problems/asteroid-collision/

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Example 4:

Input: asteroids = [-2,-1,1,2]
Output: [-2,-1,1,2]
Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.

Constraints:

2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

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
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> result;

for (int a : asteroids) {
if (a > 0)
result.push_back(a);
else {
bool explode = false;

while (!result.empty() && result.back() > 0) {
if (-a > result.back())
result.pop_back();
else if (-a < result.back()) {
explode = true;
break;
} else {
result.pop_back();
explode = true;
break;
}
}

if (explode == false)
result.push_back(a);
}
}

return result;
}
};

leetcode 1610 - Maximum Number of Visible Points

https://leetcode.com/problems/maximum-number-of-visible-points/

You are given an array points, an integer angle, and your location, where location = [posx, posy] and points[i] = [xi, yi] both denote integral coordinates on the X-Y plane.

Initially, you are facing directly east from your position. You cannot move from your position, but you can rotate. In other words, posx and posy cannot be changed. Your field of view in degrees is represented by angle, determining how wide you can see from any given view direction. Let d be the amount in degrees that you rotate counterclockwise. Then, your field of view is the inclusive range of angles [d - angle/2, d + angle/2].

You can see some set of points if, for each point, the angle formed by the point, your position, and the immediate east direction from your position is in your field of view.

There can be multiple points at one coordinate. There may be points at your location, and you can always see these points regardless of your rotation. Points do not obstruct your vision to other points.

Return the maximum number of points you can see.

Example 1:

Input: points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
Output: 3
Explanation: The shaded region represents your field of view. All points can be made visible in your field of view, including [3,3] even though [2,2] is in front and in the same line of sight.
Example 2:

Input: points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
Output: 4
Explanation: All points can be made visible in your field of view, including the one at your location.
Example 3:

Input: points = [[1,0],[2,1]], angle = 13, location = [1,1]
Output: 1
Explanation: You can only see one of the two points, as shown above.

Constraints:

1 <= points.length <= 105
points[i].length == 2
location.length == 2
0 <= angle < 360
0 <= posx, posy, xi, yi <= 100

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
class Solution {
public:
int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
vector<double> radians;

int same = 0;

for (auto &point : points) {
if (point == location)
same++;
else
radians.push_back(atan2(point[1] - location[1], point[0] - location[0]));
}

int n = radians.size();
for (int i = 0; i < n; i++)
radians.push_back(radians[i] + 2 * M_PI);

sort(radians.begin(), radians.end());

double max_radians = angle * M_PI / 180;
int ans = 0;

for (int i = 0, j = 0; j < 2 * n; j++) {
while (radians[j] - radians[i] > max_radians)
i++;

ans = max(ans, j - i + 1);
}

return ans + same;
}
};

leetcode 1509 - Minimum Difference Between Largest and Smallest Value in Three Moves

https://leetcode.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves/

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

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

Example 1:

Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.
Example 2:

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1].
The difference between the maximum and minimum is 1-0 = 1.
Example 3:

Input: nums = [6,6,0,1,1,4,6]
Output: 2
Example 4:

Input: nums = [1,5,6,14,15]
Output: 1

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//O(NlogN)
class Solution {
public:
int minDifference(vector<int>& nums) {
if (nums.size() <= 3) return 0;

sort(nums.begin(), nums.end());
int n = nums.size();

//remove 3 smallest
int diff1 = nums[n-1] - nums[3];

//remove 3 largest
int diff2 = nums[n-4] - nums[0];

//remove 1 smallest, 2 largest
int diff3 = nums[n-3] - nums[1];

//remove 2 smallest, 1 largest
int diff4 = nums[n-2] - nums[2];

return min(min(min(diff1, diff2), diff3), diff4);
}
};