Posts published in “Array”

花花酱 LeetCode 768. Max Chunks To Make Sorted II

By zxi on February 2, 2018

题目大意：给你一堆数让你分块，每块独立排序后和整个数组排序的结果相同，问你最多能分为几块。

Problem:

This question is the same as “Max Chunks to Make Sorted” except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5,4,3,2,1]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]

Output: 4

Explanation:

We can split into two chunks, such as [2, 1], [3, 4, 4].

However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

arr will have length in range [1, 2000].
arr[i] will be an integer in range [0, 10**8].

Idea:

Reduce the problem to 花花酱 769. Max Chunks To Make Sorted by creating a mapping from number to index in the sorted array.

arr = [2, 3, 5, 4, 4]

sorted = [2, 3, 4, 4, 5]

indices = [0, 1, 4, 2, 3]

Solution: Mapping

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 19 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

vector<int> v(arr.size());

std::iota(v.begin(), v.end(), 0);

std::sort(v.begin(), v.end(), [&arr](const int i1, const int i2){

return arr[i1] == arr[i2] ? (i1 < i2) : arr[i1] < arr[i2];

});

int ans = 0;

int m = 0;

for (int i = 0; i < v.size(); ++i) {

m = max(m, v[i]);

if (m == i) ++ans;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 95 ms

"""

class Solution:

def maxChunksToSorted(self, arr):

v = sorted([(n << 32) | i for i, n in enumerate(arr)])

m = 0

ans = 0

for i, n in enumerate(v):

m = max(m, n & 0xffffffff)

if i == m: ans += 1

return ans

花花酱 LeetCode 769. Max Chunks To Make Sorted

By zxi on February 2, 2018

题目大意：给你一个0 ~ n-1的排列，问你最多能分成几组，每组分别排序后能够组成0 ~ n-1。

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [4,3,2,1,0]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]

Output: 4

Explanation:

We can split into two chunks, such as [1, 0], [2, 3, 4].

However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Note:

arr will have length in range [1, 10].
arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

set<int> s;

for (int i = 0; i < arr.size(); ++i) {

s.insert(arr[i]);

if (*s.rbegin() == i) ++ans;

}

return ans;

}

};

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

int m = 0;

for (int i = 0; i < arr.size(); ++i) {

m = max(m, arr[i]);

if (m == i) ++ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 5 ms

class Solution {

public int maxChunksToSorted(int[] arr) {

int max = 0;

int ans = 0;

for (int i = 0; i < arr.length; ++i) {

max = Math.max(max, arr[i]);

if (max == i) ++ans;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 53 ms

"""

class Solution:

def maxChunksToSorted(self, arr):

m = 0

ans = 0

for i, n in enumerate(arr):

if n > m: m = n

if m == i: ans += 1

return ans

花花酱 LeetCode 766. Toeplitz Matrix

By zxi on February 2, 2018

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]

Output: True

Explanation:

1234

5123

9512

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.

Example 2:

Input: matrix = [[1,2],[2,2]]

Output: False

Explanation:

The diagonal "[1, 2]" has different elements.

Note:

matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].

Idea:

Check m[i][j] with m[i-1][j-1]

Solution: Brute Force

Time complexity: O(n*m)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

bool isToeplitzMatrix(vector<vector<int>>& matrix) {

for (int i = 1; i < matrix.size(); ++i)

for (int j = 1; j < matrix[0].size(); ++j)

if (matrix[i][j] != matrix[i - 1][j - 1]) return false;

return true;

}

};

Java

// Author: Huahua

// Running time: 29 ms

class Solution {

public boolean isToeplitzMatrix(int[][] matrix) {

for (int i = 1; i < matrix.length; ++i)

for (int j = 1; j < matrix[0].length; ++j)

if (matrix[i][j] != matrix[i - 1][j - 1]) return false;

return true;

}

Python3

"""

Author: Huahua

Running time: 99 ms

"""

class Solution:

def isToeplitzMatrix(self, matrix):

m = len(matrix)

n = len(matrix[0])

for i in range(1, m):

for j in range(1, n):

if matrix[i][j] != matrix[i - 1][j - 1]: return False

return True

花花酱 LeetCode 480. Sliding Window Median

By zxi on January 28, 2018

题目大意：让你求移动窗口的中位数。

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Median

--------------- -----

[1 3 -1] -3 5 3 6 7 1

1 [3 -1 -3] 5 3 6 7 -1

1 3 [-1 -3 5] 3 6 7 -1

1 3 -1 [-3 5 3] 6 7 3

1 3 -1 -3 [5 3 6] 7 5

1 3 -1 -3 5 [3 6 7] 6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.

Solution 0: Brute Force

Time complexity: O(n*klogk) TLE 32/42 test cases passed

Solution 1: Insertion Sort

Time complexity: O(k*logk + (n – k + 1)*k)

Space complexity: O(k)

C++ / vector

// Author: Huahua

// Running time: 99 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

std::sort(window.begin(), window.end());

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::find(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

C++ / vector + binary_search for deletion.

// Author: Huahua

// Running time: 84 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

std::sort(window.begin(), window.end());

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::lower_bound(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 60 ms

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

for (int i = 0; i < k; ++i)

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = 0;

while (i < window.length - 1 && val > window[i]) ++i;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = 0;

while (i < window.length && val != window[i]) ++i;

while (i < window.length - 1) window[i] = window[++i];

}

Java / Binary Search

// Author: Huahua

// Running time: 47 ms (<98.96%)

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

for (int i = 0; i < k; ++i)

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

if (i < 0) i = - i - 1;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

while (i < window.length - 1) window[i] = window[++i];

}

Python

"""

Author: Huahua

Running time: 161 ms (< 93.75%)

"""

class Solution:

def medianSlidingWindow(self, nums, k):

if k == 0: return []

ans = []

window = sorted(nums[0:k])

for i in range(k, len(nums) + 1):

ans.append((window[k // 2] + window[(k - 1) // 2]) / 2.0)

if i == len(nums): break

index = bisect.bisect_left(window, nums[i - k])

window.pop(index)

bisect.insort_left(window, nums[i])

return ans

Solution 2: BST

// Author: Huahua

// Running time: 68 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

multiset<int> window(nums.begin(), nums.begin() + k);

auto mid = next(window.begin(), (k - 1) / 2);

for (int i = k; i <= nums.size(); ++i) {

ans.push_back((static_cast<double>(*mid) +

*next(mid, (k + 1) % 2)) / 2.0);

if (i == nums.size()) break;

window.insert(nums[i]);

if (nums[i] < *mid) --mid;

if (nums[i - k] <= *mid) ++mid;

window.erase(window.lower_bound(nums[i - k]));

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 239. Sliding Window Maximum

By zxi on January 24, 2018

题目大意：给你一个数组，让你输出移动窗口的最大值。

Problem:

https://leetcode.com/problems/sliding-window-maximum/

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Idea:

Solution 1: Brute Force

Time complexity: O((n – k + 1) * k)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 180 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

for (int i = k - 1; i < nums.size(); ++i) {

ans.push_back(*max_element(nums.begin() + i - k + 1, nums.begin() + i + 1));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 80 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return new int[0];

int[] ans = new int[nums.length - k + 1];

for (int i = k - 1; i < nums.length; ++i) {

int maxNum = nums[i];

for (int j = 1; j < k; ++j)

if (nums[i - j] > maxNum) maxNum = nums[i - j];

ans[i - k + 1] = maxNum;

}

return ans;

}

Python

"""

Author: Huahua

Running time: 1044 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

if not nums: return []

return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

Solution 2: BST

Time complexity: O((n – k + 1) * logk)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

vector<int> ans;

if (nums.empty()) return ans;

multiset<int> window(nums.begin(), nums.begin() + k - 1);

for (int i = k - 1; i < nums.size(); ++i) {

window.insert(nums[i]);

ans.push_back(*window.rbegin());

if (i - k + 1 >= 0)

window.erase(window.equal_range(nums[i - k + 1]).first);

}

return ans;

}

};

Solution 3: Monotonic Queue

Time complexity: O(n)

Space complexity: O(k)

C++

// Author: Huahua

// Running time: 70 ms

class MonotonicQueue {

public:

void push(int e) {

while(!data_.empty() && e > data_.back()) data_.pop_back();

data_.push_back(e);

}

void pop() {

data_.pop_front();

}

int max() const { return data_.front(); }

private:

deque<int> data_;

};

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

MonotonicQueue q;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

q.push(nums[i]);

if (i - k + 1 >= 0) {

ans.push_back(q.max());

if (nums[i - k + 1] == q.max()) q.pop();

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 65 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> index;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

while (!index.empty() && nums[i] >= nums[index.back()]) index.pop_back();

index.push_back(i);

if (i - k + 1 >= 0) ans.push_back(nums[index.front()]);

if (i - k + 1 >= index.front()) index.pop_front();

}

return ans;

}

};

C++ V3

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {

deque<int> q;

vector<int> ans;

for (int i = 0; i < nums.size(); ++i) {

while (!q.empty() && nums[i] > q.back()) q.pop_back();

q.push_back(nums[i]);

const int s = i - k + 1;

if (s < 0) continue;

ans.push_back(q.front());

if (nums[s] == q.front()) q.pop_front();

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 19 ms

class Solution {

public int[] maxSlidingWindow(int[] nums, int k) {

if (k == 0) return nums;

int[] ans = new int[nums.length - k + 1];

Deque<Integer> indices = new LinkedList<>();

for (int i = 0; i < nums.length; ++i) {

while (indices.size() > 0 && nums[i] >= nums[indices.getLast()])

indices.removeLast();

indices.addLast(i);

if (i - k + 1 >= 0) ans[i - k + 1] = nums[indices.getFirst()];

if (i - k + 1 >= indices.getFirst()) indices.removeFirst();

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 238 ms

"""

class MaxQueue:

def __init__(self):

self.q_ = collections.deque()

def push(self, e):

while self.q_ and e > self.q_[-1]: self.q_.pop()

self.q_.append(e)

def pop(self):

self.q_.popleft()

def max(self):

return self.q_[0]

class Solution:

def maxSlidingWindow(self, nums, k):

q = MaxQueue()

ans = []

for i in range(len(nums)):

q.push(nums[i])

if i >= k - 1:

ans.append(q.max())

if nums[i - k + 1] == q.max(): q.pop()

return ans

Python3 V2

"""

Author: Huahua

Running time: 193 ms

"""

class Solution:

def maxSlidingWindow(self, nums, k):

indices = collections.deque()

ans = []

for i in range(len(nums)):

while indices and nums[i] >= nums[indices[-1]]: indices.pop()

indices.append(i)

if i >= k - 1: ans.append(nums[indices[0]])

if i - k + 1 == indices[0]: indices.popleft()

return ans