766. Toeplitz Matrix

難度: Easy

類型: Array,Matrix 

CPP程式下載: 766.cpp

Topic:

Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false.

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

 

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
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.

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 20
• 0 <= matrix[i][j] <= 99

 

Follow up:

• What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
• What if the matrix is so large that you can only load up a partial row into the memory at once?

Consideration:

1. "Union of first column and first row elements".

2. Check each elements in the union from its left upper to right bottom diagonal direction. If each element's diagonal values are the same, then return true. If any different value is found, return false.

 

Code:

class Solution {

public:

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

        int m = matrix.size();

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

        //cout << "m = " << m << ", n = "<< n << "\n";

        //bool result = true;

        int i,j,k,value;

        for (k=0;k<m;k++)

        {

            j=0;

            i=k;

            value=matrix[i][j];

            i++;

            j++;

            while (j<n && i<m)

            {

                //cout << "i = " << i << ", j = "<< j << "\n";

                if (matrix[i][j]==value)

                {

                    i++;

                    j++;

                }

                else

                {

                    return false;

                }

            }

        }

        for (k=1;k<n;k++)

        {

            i=0;

            j=k;

            value=matrix[i][j];

            i++;

            j++;

            while (j<n && i<m)

            {

                //cout << "i = " << i << ", j = "<< j << "\n";

                if (matrix[i][j]==value)

                {

                    i++;

                    j++;

                }

                else

                {

                    return false;

                }

            }

        }

        return true;

    }

};

Result:

Accepted

483 / 483 testcases passed

tendchen

submitted at Mar 06, 2026 16:18

Runtime

0ms

Beats100.00%

Memory

21.12MB

Beats28.29%

378. Kth Smallest Element in a Sorted Matrix

難度: Middle

類型: Array,Binary Search,Sorting,Heap (Priority Queue),Matrix,

CPP程式下載: 378.cpp

Topic:

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

You must find a solution with a memory complexity better than O(n2).

 

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Example 2:

Input: matrix = [[-5]], k = 1
Output: -5

 

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -109 <= matrix[i][j] <= 109
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n2

 

Follow up:

• Could you solve the problem with a constant memory (i.e., O(1) memory complexity)?
• Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.

Consideration:

1. No create new vector or multiset to save memory.

2. Binary search to save time/complexity. (mid value from left-smallest to right-largest)

3. left-upper corner is the smallest value, and right-bottom corner is the largest value.

4. When [left to middle] number counts are more than k, k smallest value is in the [left to middle] part. otherwise, it would be in the [middle+1 to right] part.

5. When matrix[i][j] < middle, it means all element at matrix(i, 0~j) will be less than middle. Then you may check next column matrix(i+1, 0~j).

Code:

class Solution {

public:

    int kthSmallest(vector<vector<int>>& matrix, int k) {

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

cout << "n = " << n << "\n";

        int left = matrix[0][0];

        int right = matrix[n-1][n-1];

        int mid;

        while (left<right)

        {

            mid = (left + right)>>1;

            if (left_check(matrix, mid, k, n))

            {

                right = mid;

            }

            else

            {

                left = mid + 1;

            }

        }

return left;

    }

private:

    bool left_check(vector<vector<int>>& matrix, int mid, int k, int n)

    {

        int count=0;

        int i=n-1;

        int j=0;

        while ((j<n) && (i>=0))

        {

            if (mid>=matrix[i][j])

            {

                count+=(i+1);

                ++j;

            }

            else

                --i;

        }

        return count >= k;

    }

};

Result:

Accepted

87 / 87 testcases passed

tendchen

submitted at Mar 06, 2026 15:32

Runtime

0ms

Beats100.00%

Memory

17.06MB

Beats80.01%