LeetCode(75) -- 36, 34

P36. Valid Sudoku (Medium)

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

My Solution

public class P36_ValidSudoku {
    public boolean isValidSudoku(char[][] board) {
        if (!checkRowOrColumn(board, true)) {
            return false;
        }
        if (!checkRowOrColumn(board, false)) {
            return false;
        }
        for (int i = 0; i < 9; i++) {
            if (!checkSub(board, i)) {
                return false;
            }
        }
        return true;
    }

    private boolean checkSub(char[][] board, int boxNumber) {
        int row = (boxNumber / 3) * 3;
        int col = (boxNumber % 3) * 3;
        boolean[] test = new boolean[9];
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                char c = board[i][j];
                if (c == '.') {
                    continue;
                }
                int index = c - '1';
                if (test[index]) {
                    return false;
                }
                test[index] = true;
            }
        }
        return true;
    }

    private boolean checkRowOrColumn(char[][] board, boolean row) {
        for (int i = 0; i < 9; i++) {
            boolean[] test = new boolean[9];
            for (int j = 0; j < 9; j++) {
                char c;
                if (row) {
                    c = board[i][j];
                } else {
                    c = board[j][i];
                }
                if (c == '.') {
                    continue;
                }
                int index = c - '1';
                if (test[index]) {
                    return false;
                }
                test[index] = true;
            }
        }
        return true;
    }
}

100%

The Best Solution

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < board.length; i++) {
            if(!validRow(board,i)) return false;
            if(!validCol(board,i)) return false;
        }
        for(int i = 0; i < board.length; i+=3) {
            for(int c = 0; c < board[0].length; c+=3) {
                if(!validBox(board,i,c)) return false;
            }
        }
        return true;
    }
    
    private boolean validRow(char[][] board, int r) {
        boolean[] seen = new boolean[9];
        for(int c = 0; c < board[0].length; c++) {
            if(board[r][c] != '.') {
                if(seen[board[r][c]-'1']) return false;
                seen[board[r][c]-'1'] = true;
            }
        }
        return true;
    }
    
    private boolean validCol(char[][] board, int c) {
        boolean[] seen = new boolean[9];
        for(int r = 0; r < board.length; r++) {
            if(board[r][c] != '.') {
                if(seen[board[r][c]-'1']) return false;
                seen[board[r][c]-'1'] = true;
            }
        }
        return true;
    }
    
    private boolean validBox(char[][] board, int r, int c) {
        boolean[] seen = new boolean[9];
        for(int i = r; i < r+3; i++) {
            for(int j = c; j < c+3; j++) {
                if(board[i][j] != '.') {
                    if(seen[board[i][j]-'1']) return false;
                    seen[board[i][j]-'1'] = true;
                }
            }
        }
        return true;
    }
}

P34. Find First and Last Position of Element in Sorted Array (Medium)

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

My Solution

public class P34_FindFirstAndLastPositionOfElementInSortedArray {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        int i = binarySearch(nums, target);
        if (i == -1) {
            return new int[] {-1, -1};
        }
        int l = i, r = i;
        while (l > 0 && nums[l-1] == target) {
            l--;
        }
        while (r < nums.length - 1 && nums[r+1] == target) {
            r++;
        }
        ans[0] = l;
        ans[1] = r;
        return ans;
    }

    private int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ints = new P34_FindFirstAndLastPositionOfElementInSortedArray().searchRange(new int[]{1}, 1);
        System.out.println("ints = " + Arrays.toString(ints));

    }
}

100%

The Best Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0) return new int[]{-1,-1};
        int l = 0;
        int r = nums.length - 1;
        
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                l = mid;
                break;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        if (nums[l] != target) return new int[] {-1, -1};
        int[] range = new int[]{l, l};
        while(range[0] > 0 && nums[range[0]-1] == target) range[0]--;
        while(range[1] < nums.length-1 && nums[range[1]+1] == target) range[1]++;
        return range;
    }
}