Minimum Time to Visit All Points

Given integer coordinates points[i] = [xi, yi] for n points on a plane, calculate the minimum time in seconds to visit all points in the order given.

Movement rules:

• Each second, move one unit horizontally, vertically, or diagonally (one unit in both directions).

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7

Explenation: An optimal path: [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]. From [1,1] to [3,4] takes 3 seconds, from [3,4] to [-1,0] takes 4 seconds, total 7 seconds.

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5

Constraints:

• n == points.length, 1 <= n <= 100
• points[i].length == 2
• -1000 <= xi, yi <= 1000

Solution:

The time between two consecutive points (x1,y1) and (x2,y2) is max(|x1 - x2|, |y1 - y2|) because diagonal moves cover both axes simultaneously.

var minTimeToVisitAllPoints = function(points) {
    let total = 0;
    for (let i = 1; i < points.length; i++) {
        total += Math.max(
            Math.abs(points[i-1][0] - points[i][0]),
            Math.abs(points[i-1][1] - points[i][1])
        );
    }
    return total;
};

class Solution(object):
    def minTimeToVisitAllPoints(self, points):
        total = 0
        prev = points[0]
        for p in points:
            dx = abs(p[0] - prev[0])
            dy = abs(p[1] - prev[1])
            total += min(dx, dy) + abs(dx - dy)  # equivalent to max(dx, dy)
            prev = p
        return total

The approach iterates through the array once, computing the Chebyshev distance between successive points.

Search Suggestions System

Given an array of product strings products and a searchWord, design a recommendation system that, after typing each character of the search word, returns up to three product names from products that share the prefix with the typed characters, sorted lexicographically.

Return a list of lists of strings for each prefix length.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
  ["mobile","moneypot","monitor"],
  ["mobile","moneypot","monitor"],
  ["mouse","mousepad"],
  ["mouse","mousepad"],
  ["mouse","mousepad"]
]

Explanation: After sorting lexicographically: ["mobile","moneypot","monitor","mouse","mousepad"]. For prefixes "m" and "mo", all products match, so the three smallest are returned. For "mou", "mous", "mouse", only "mouse" and "mousepad" match.

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

• 1 <= products.length <= 1000
• Sum of product lengths <= 2 * 10^4
• All characters are lowercase English letters.
• 1 <= searchWord.length <= 1000

Solution:

Sort the products lexicographically. Then for each prefix of the search word, filter the sorted list to only those that start with that prefix, taking the first three.

var suggestedProducts = function(products, searchWord) {
    products.sort();
    const result = [];
    let previousMatches = products;
    for (let i = 0; i < searchWord.length; i++) {
        const currentMatches = [];
        for (let j = 0; j < previousMatches.length; j++) {
            if (previousMatches[j][i] === searchWord[i]) {
                currentMatches.push(previousMatches[j]);
            }
        }
        result.push(currentMatches.slice(0, 3));
        previousMatches = currentMatches;
    }
    return result;
};

The code maintains a filtered list as the prefix grows, reducing the search space.

Find Winner on a Tic-Tac-Toe Game

Tic-tac-toe is played on a 3x3 grid. Player A uses 'X', player B uses 'O'. Players alternate placing their marks on empty cells. The game ends when three same marks align horizontally, vertically, or diagonally, or when all cells are filled.

Given an array moves where each element is [row, col] representing the sequence of moves (starting with A), return the winner ('A' or 'B'), 'Draw' if the board is full with no winner, or 'Pending' if the game is not over.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"

Constraints:

• 1 <= moves.length <= 9
• Moves are valid and no duplicates.

Solution:

Simulate the board. After each move, check for winning condition. If the board is full after all moves and no winner, it's a draw.

var tictactoe = function(moves) {
    const board = Array.from({length: 3}, () => Array(3).fill(''));
    for (let i = 0; i < moves.length; i++) {
        const [r, c] = moves[i];
        board[r][c] = i % 2 === 0 ? 'A' : 'B';
        if (checkWin(board, r, c)) {
            return board[r][c];
        }
    }
    return moves.length === 9 ? 'Draw' : 'Pending';
};

function checkWin(board, row, col) {
    const player = board[row][col];
    // Check row
    if (board[row].every(cell => cell === player)) return true;
    // Check column
    if (board.every(r => r[col] === player)) return true;
    // Check main diagonal
    if (row === col && board[0][0] === player && board[1][1] === player && board[2][2] === player) return true;
    // Check anti-diagonal
    if (row + col === 2 && board[0][2] === player && board[1][1] === player && board[2][0] === player) return true;
    return false;
}

class Solution {
    public String tictactoe(int[][] moves) {
        int[][] board = new int[3][3]; // 0 empty, 1 for A, -1 for B
        for (int i = 0; i < moves.length; i++) {
            int player = (i % 2 == 0) ? 1 : -1;
            board[moves[i][0]][moves[i][1]] = player;
            if (hasWon(board, player)) {
                return (player == 1) ? "A" : "B";
            }
        }
        return moves.length == 9 ? "Draw" : "Pending";
    }
    
    private boolean hasWon(int[][] board, int player) {
        // Check rows and columns
        for (int i = 0; i < 3; i++) {
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
            if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
        }
        // Diagonals
        if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
        if (board[0][2] == player && board[1][1] == player && board[2][0] == player) return true;
        return false;
    }
}

Both implementations rely on checking win conditions after each move, using the fact that only the most recent move can create a win.