Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
Logic Building Questions for week 2
Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
1
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
L1
Input: matrix = [[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]
Constraints:
m == [Link]
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Richest Customer Wealth
You are given an (m* n) integer grid accounts where accounts[i][j] is the amount of money
the ith customer has in the jth bank. Return the wealth that the richest customer has.
A customer's wealth is the amount of money they have in all their bank accounts. The richest
customer is the customer that has the maximum wealth.
Example 1: L2
2 Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.
Example 2:
Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation:
1st customer has wealth = 6
2nd customer has wealth = 10
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.
Example 3:
Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17
Constraints:
m == [Link]
n == accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100
Toeplitz Matrix
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:
3 L1
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 == [Link]
n == matrix[i].length
1 <= m, n <= 20
0 <= matrix[i][j] <= 99
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
4 Game of Life L1
According to Wikipedia's article: "The Game of Life, also known simply as Life, is a
cellular automaton devised by the British mathematician John Horton Conway in
1970."
The board is made up of an m x n grid of cells, where each cell has an initial state:
live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight
neighbors (horizontal, vertical, diagonal) using the following four rules (taken from
the above Wikipedia article):
1. Any live cell with fewer than two live neighbors dies as if caused by under-
population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-
population.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by
reproduction.
The next state is created by applying the above rules simultaneously to every cell in
the current state, where births and deaths occur simultaneously. Given the current
state of the m x n grid board, return the next state.
Example 1:
Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
Example 2:
Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]
Constraints:
m == [Link]
n == board[i].length
1 <= m, n <= 25
board[i][j] is 0 or 1.
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
Follow up:
Could you solve it in-place? Remember that the board needs to be updated
simultaneously: You cannot update some cells first and then use their updated values
to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is
infinite, which would cause problems when the active area encroaches upon the
border of the array (i.e., live cells reach the border). How would you address these
problems?
5 Count Negative Numbers in a Sorted Matrix
Given a m x n matrix grid which is sorted in non-increasing order both row-wise and
column-wise, return the number of negative numbers in grid.
Example 1:
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.
Example 2: L2
Input: grid = [[3,2],[1,0]]
Output: 0
Constraints:
m == [Link]
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
Follow up: Could you find an O(n + m) solution?
Soution 1.
1. #include <stdio.h>
2.
3. void printSpiral(int m, int n, int matrix[m][n]) {
4. int top = 0, bottom = m - 1;
5. int left = 0, right = n - 1;
6. int i;
7.
8. while (top <= bottom && left <= right) {
9. // Print the top row from the remaining rows
10. for (i = left; i <= right; i++) {
11. printf("%d ", matrix[top][i]);
12. }
13. top++;
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
14.
15. // Print the right column from the remaining columns
16. for (i = top; i <= bottom; i++) {
17. printf("%d ", matrix[i][right]);
18. }
19. right--;
20.
21. // Print the bottom row from the remaining rows (if any)
22. if (top <= bottom) {
23. for (i = right; i >= left; i--) {
24. printf("%d ", matrix[bottom][i]);
25. }
26. bottom--;
27. }
28.
29. // Print the left column from the remaining columns (if any)
30. if (left <= right) {
31. for (i = bottom; i >= top; i--) {
32. printf("%d ", matrix[i][left]);
33. }
34. left++;
35. }
36. }
37. }
38.
39. int main() {
40. // Example 1
41. int matrix1[3][3] = {
42. {1, 2, 3},
43. {4, 5, 6},
44. {7, 8, 9}
45. };
46. int m1 = 3, n1 = 3;
47. printf("Spiral Order of Example 1: ");
48. printSpiral(m1, n1, matrix1);
49. printf("\n");
50.
51. // Example 2
52. int matrix2[3][4] = {
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
53. {1, 2, 3, 4},
54. {5, 6, 7, 8},
55. {9, 10, 11, 12}
56. };
57. int m2 = 3, n2 = 4;
58. printf("Spiral Order of Example 2: ");
59. printSpiral(m2, n2, matrix2);
60. printf("\n");
61.
62. return 0;
63. }
Solution -2.
1. #include <stdio.h>
2.
3. int maximumWealth(int m, int n, int accounts[m][n]) {
4. int maxWealth = 0;
5.
6. for (int i = 0; i < m; i++) {
7. int customerWealth = 0;
8. for (int j = 0; j < n; j++) {
9. customerWealth += accounts[i][j];
10. }
11. if (customerWealth > maxWealth) {
12. maxWealth = customerWealth;
13. }
14. }
15.
16. return maxWealth;
17. }
18.
19. int main() {
20. // Example 1
21. int accounts1[2][3] = {
22. {1, 2, 3},
23. {3, 2, 1}
24. };
25. int m1 = 2, n1 = 3;
26. printf("Richest Customer Wealth (Example 1): %d\n", maximumWealth(m1, n1, accounts1));
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
27.
28. // Example 2
29. int accounts2[3][2] = {
30. {1, 5},
31. {7, 3},
32. {3, 5}
33. };
34. int m2 = 3, n2 = 2;
35. printf("Richest Customer Wealth (Example 2): %d\n", maximumWealth(m2, n2, accounts2));
36.
37. // Example 3
38. int accounts3[3][3] = {
39. {2, 8, 7},
40. {7, 1, 3},
41. {1, 9, 5}
42. };
43. int m3 = 3, n3 = 3;
44. printf("Richest Customer Wealth (Example 3): %d\n", maximumWealth(m3, n3, accounts3));
45.
46. return 0;
47. }
Solution-3.
1. #include <stdio.h>
2. #include <stdbool.h>
3.
4. bool isToeplitzMatrix(int m, int n, int matrix[m][n]) {
5. for (int i = 1; i < m; i++) {
6. for (int j = 1; j < n; j++) {
7. // Check if each element matches the element diagonally above and to the left
8. if (matrix[i][j] != matrix[i - 1][j - 1]) {
9. return false;
10. }
11. }
12. }
13. return true;
14. }
15.
16. int main() {
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
17. // Example 1
18. int matrix1[3][4] = {
19. {1, 2, 3, 4},
20. {5, 1, 2, 3},
21. {9, 5, 1, 2}
22. };
23. int m1 = 3, n1 = 4;
24. printf("Is Example 1 Toeplitz? %s\n", isToeplitzMatrix(m1, n1, matrix1) ? "true" : "false");
25.
26. // Example 2
27. int matrix2[2][2] = {
28. {1, 2},
29. {2, 2}
30. };
31. int m2 = 2, n2 = 2;
32. printf("Is Example 2 Toeplitz? %s\n", isToeplitzMatrix(m2, n2, matrix2) ? "true" : "false");
33.
34. return 0;
35. }
Solution 4 .
1. #include <stdio.h>
2.
3. #define LIVE 1
4. #define DEAD 0
5.
6. void gameOfLife(int m, int n, int board[m][n]) {
7. // Directions arrays to navigate 8 neighbors
8. int directions[8][2] = {
9. {-1, -1}, {-1, 0}, {-1, 1},
10. {0, -1}, {0, 1},
11. {1, -1}, {1, 0}, {1, 1}
12. };
13.
14. // Update the board in-place using temporary states:
15. // 2 means a live cell that dies
16. // 3 means a dead cell that becomes live
17. for (int i = 0; i < m; i++) {
18. for (int j = 0; j < n; j++) {
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
19. int liveNeighbors = 0;
20.
21. // Count live neighbors
22. for (int d = 0; d < 8; d++) {
23. int ni = i + directions[d][0];
24. int nj = j + directions[d][1];
25.
26. if (ni >= 0 && ni < m && nj >= 0 && nj < n && (board[ni][nj] == LIVE || board[ni][nj] ==
2)) {
27. liveNeighbors++;
28. }
29. }
30.
31. // Apply rules
32. if (board[i][j] == LIVE) {
33. // Rule 1 or Rule 3
34. if (liveNeighbors < 2 || liveNeighbors > 3) {
35. board[i][j] = 2; // Mark as live -> dead
36. }
37. } else {
38. // Rule 4
39. if (liveNeighbors == 3) {
40. board[i][j] = 3; // Mark as dead -> live
41. }
42. }
43. }
44. }
45.
46. // Finalize the board updates
47. for (int i = 0; i < m; i++) {
48. for (int j = 0; j < n; j++) {
49. if (board[i][j] == 2) {
50. board[i][j] = DEAD;
51. } else if (board[i][j] == 3) {
52. board[i][j] = LIVE;
53. }
54. }
55. }
56. }
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
57.
58. // Function to print the board
59. void printBoard(int m, int n, int board[m][n]) {
60. for (int i = 0; i < m; i++) {
61. for (int j = 0; j < n; j++) {
62. printf("%d ", board[i][j]);
63. }
64. printf("\n");
65. }
66. }
67.
68. int main() {
69. // Example 1
70. int board1[4][3] = {
71. {0, 1, 0},
72. {0, 0, 1},
73. {1, 1, 1},
74. {0, 0, 0}
75. };
76. int m1 = 4, n1 = 3;
77. printf("Original Board (Example 1):\n");
78. printBoard(m1, n1, board1);
79. gameOfLife(m1, n1, board1);
80. printf("Next State Board (Example 1):\n");
81. printBoard(m1, n1, board1);
82.
83. // Example 2
84. int board2[2][2] = {
85. {1, 1},
86. {1, 0}
87. };
88. int m2 = 2, n2 = 2;
89. printf("\nOriginal Board (Example 2):\n");
90. printBoard(m2, n2, board2);
91. gameOfLife(m2, n2, board2);
92. printf("Next State Board (Example 2):\n");
93. printBoard(m2, n2, board2);
94.
95. return 0;
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
96. }
Solution -5.
1. #include <stdio.h>
2.
3. int countNegatives(int m, int n, int grid[m][n]) {
4. int count = 0;
5. int row = 0, col = n - 1; // Start from the top-right corner
6.
7. while (row < m && col >= 0) {
8. if (grid[row][col] < 0) {
9. // If the current element is negative, all elements below in this column are also negative
10. count += (m - row);
11. col--; // Move left to check for more negatives in the current row
12. } else {
13. // Move down to the next row if the current element is non-negative
14. row++;
15. }
16. }
17.
18. return count;
19. }
20.
21. int main() {
22. // Example 1
23. int grid1[4][4] = {
24. {4, 3, 2, -1},
25. {3, 2, 1, -1},
26. {1, 1, -1, -2},
27. {-1, -1, -2, -3}
28. };
29. int m1 = 4, n1 = 4;
30. printf("Number of negative numbers in Example 1: %d\n", countNegatives(m1, n1, grid1));
31.
32. // Example 2
33. int grid2[2][2] = {
34. {3, 2},
35. {1, 0}
36. };
Galgotias College of Engineering & Technology, Greater Noida
CSE-Training & Development Center
37. int m2 = 2, n2 = 2;
38. printf("Number of negative numbers in Example 2: %d\n", countNegatives(m2, n2, grid2));
39.
40. return 0;
41. }