Valid Sudoku | Given an array of integers nums
sorted in non-decreasing order, find the starting and ending position of a given target
value.
If target
is not found in the array, return [-1, -1]
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
Valid Sudoku LeetCode Solution
✅Time: O(1)
✅Space:O(1)
C++
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
unordered_set<string> seen;
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.')
continue;
const string c(1, board[i][j]);
if (!seen.insert(c + "@row" + to_string(i)).second ||
!seen.insert(c + "@col" + to_string(j)).second ||
!seen.insert(c + "@box" + to_string(i / 3) + to_string(j / 3))
.second)
return false;
}
return true;
}
};
Java
class Solution {
public boolean isValidSudoku(char[][] board) {
Set<String> seen = new HashSet<>();
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.')
continue;
final char c = board[i][j];
if (!seen.add(c + "@row" + i) ||
!seen.add(c + "@col" + j) ||
!seen.add(c + "@box" + i / 3 + j / 3))
return false;
}
return true;
}
}
Python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
seen = set()
for i in range(9):
for j in range(9):
c = board[i][j]
if c == '.':
continue
if c + '@row ' + str(i) in seen or \
c + '@col ' + str(j) in seen or \
c + '@box ' + str(i // 3) + str(j // 3) in seen:
return False
seen.add(c + '@row ' + str(i))
seen.add(c + '@col ' + str(j))
seen.add(c + '@box ' + str(i // 3) + str(j // 3))
return True
Watch Tutorial
Checkout more Solutions here