花花酱 LeetCode 59. Spiral Matrix II

By zxi on September 29, 2019

Given a positive integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution: Simulation

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int> > generateMatrix(int n) {

vector<vector<int>> ans(n, vector<int>(n));

int dir = 2, x = 0, y = 0;

int max_x = n - 1, max_y = n - 1;

int min_x = 0, min_y = 1;

int i = 0;

while (++i <= n*n) {

ans[y][x] = i;

switch (dir) {

// up

case 1: if (--y == min_y) { dir = 2; ++min_y; } break;

// right

case 2: if (++x == max_x) { dir = 3; --max_x; } break;

// down

case 3: if (++y == max_y) { dir = 4; --max_y; } break;

// left

case 4: if (--x == min_x) { dir = 1; ++min_x; } break;

}

return ans;

}

};

花花酱 LeetCode 54. Spiral Matrix

By zxi on April 12, 2019

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Solution: Simulation

Keep track of the current bounds (left, right, top, bottom).

Init: left = 0, right = n – 1, top = 0, bottom = m – 1

Each time we move in one direction and shrink the bounds and turn 90 degrees:
1. go right => –top
2. go down => –right
3. go left => ++bottom
4. go up => ++left

C++

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

int l = 0;

int t = 0;

int r = matrix[0].size();

int b = matrix.size();

const int total = (r--) * (b--);

int d = 0;

int x = 0;

int y = 0;

vector<int> ans;

while (ans.size() < total - 1) {

if (d == 0) {

while (x < r) ans.push_back(matrix[y][x++]);

++t;

} else if (d == 1) {

while (y < b) ans.push_back(matrix[y++][x]);

--r;

} else if (d == 2) {

while (x > l) ans.push_back(matrix[y][x--]);

--b;

} else if (d == 3) {

while (y > t) ans.push_back(matrix[y--][x]);

++l;

}

d = (d + 1) % 4;

}

if (ans.size() != total) ans.push_back(matrix[y][x]);

return ans;

}

};

花花酱 LeetCode 74. Search a 2D Matrix

By zxi on February 13, 2019

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 3

Output: true

Example 2:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 13

Output: false

Solution: Binary Search

Treat the 2D array as a 1D array. matrix[index / cols][index % cols]

Time complexity: O(log(m*n))
Space complexity: O(1)

C++

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty()) return false;

int l = 0;

int r = matrix.size() * matrix[0].size();

const int cols = matrix[0].size();

while (l < r) {

const int m = l + (r - l) / 2;

if (matrix[m / cols][m % cols] == target) {

return true;

} else if (matrix[m / cols][m % cols] > target) {

r = m;

} else {

l = m + 1;

}

return false;

}

};

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

By zxi on September 10, 2018

Problem

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

The m and n will be in the range [1, 30000].
The k will be in the range [1, m * n]

Solution 1: Nth element (MLE)

Time complexity: O(mn)

Space complexity: O(mn)

C++

// 59 / 69 test cases passed.

class Solution {

public:

int findKthNumber(int m, int n, int k) {

vector<int> s(m * n);

auto it = begin(s);

for (int i = 1; i <= m; ++i)

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

*it++ = i * j;

nth_element(begin(s), begin(s) + k - 1, end(s));

return s[k - 1];

}

};

Solution2 : Binary Search

Find first x such that there are k elements less or equal to x in the table.

Time complexity: O(m*log(m*n))

Space complexity: O(1)

C++

// Author: Huahua, 12 ms

class Solution {

public:

int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

int x = l + (r - l) / 2;

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

private:

// Returns # of elements in the m*n table that are <= x

int LEX(int m, int n, int x) {

int count = 0;

for (int i = 1; i <= m; ++i)

count += min(n, x / i);

return count;

}

};

Java

// Author: Huahua, 16 ms

class Solution {

public int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

int x = l + (r - l) / 2;

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

// Returns # of elements in the m*n table that are <= x

private int LEX(int m, int n, int x) {

int count = 0;

for (int i = 1; i <= m; ++i)

count += Math.min(n, x / i);

return count;

}

Python3

# Author: Huahua, 976 ms

class Solution:

def findKthNumber(self, m, n, k):

def LEX(m, n, x, k):

count = 0

for i in range(1, min(m + 1, x + 1)):

count += min(n, x // i)

if count >= k: return count

return count

l = 1

r = m * n + 1

while l < r:

x = l + (r - l) // 2

if LEX(m, n, x, k) >= k:

r = x

else:

l = x + 1

return l

Problem

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

Input: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
Output: 
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:

The height and width of the given matrix is in range [1, 100].
The given r and c are all positive.

Solution1: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {

if (nums.size() == 0) return nums;

int m = nums.size();

int n = nums[0].size();

if (m * n != r * c) return nums;

// new matrix r*c

vector<vector<int>> ans(r, vector<int>(c));

for(int i = 0; i < m * n;++i) {

int src_y = i / n;

int src_x = i % n;

int dst_y = i / c;

int dst_x = i % c;

ans[dst_y][dst_x] = nums[src_y][src_x];

}

return ans;

}

};

Posts tagged as “matrix”

花花酱 LeetCode 59. Spiral Matrix II

Solution: Simulation

C++

花花酱 LeetCode 54. Spiral Matrix

C++

花花酱 LeetCode 74. Search a 2D Matrix

Solution: Binary Search

C++

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

Problem

Solution 1: Nth element (MLE)

C++

Solution2 : Binary Search

C++

Java

Python3

Related Problems

花花酱 LeetCode 566. Reshape the Matrix

Problem

Solution1: Brute Force