419. Battleships in a Board

 Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
• At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

...X
XXXX
...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

Solution:

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int ans = 0;
        
        int rows = board.size();
        if (rows == 0) {
            return 0;
        }
        int cols = board[0].size();
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'X') {
                    ans++;
                    if (check_right(board, i, j+1)) {
                        continue;
                    }
                    if (check_bottom(board, i+1, j)) {
                        continue;
                    }
                }
            }
        }
        return ans;
    }
    
    bool check_right(vector<vector<char>>& board, int i, int j) {
        if (j == board[0].size()) {
            return false;
        }
        bool flag = false;
        while (j < board[0].size() && board[i][j] == 'X') {
            board[i][j] = '.';
            j++;
            flag = true;
        }
        return flag;
    }
    bool check_bottom(vector<vector<char>>& board, int i, int j) {
        if (i == board.size()) {
            return false;
        }
        bool flag = false;
        while (i < board.size() && board[i][j] == 'X') {
            board[i][j] = '.';
            i++;
            flag = true;
        }
        return flag;
    }
};

======== One iteration and constant space and without modifying the board ====

int countBattleships(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return 0;
        int res = 0, m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '.' || (i > 0 && board[i - 1][j] == 'X') || (j > 0 && board[i][j - 1] == 'X')) continue;
                ++res;
            }
        }
        return res;
    }

994. Rotting Oranges

 In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

 

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

 

Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] is only 0, 1, or 2.

class Solution {

public:

    bool valid(vector<vector<int>>& grid, int new_x, int new_y) {

        if (new_x < 0 || new_x >= grid.size() || new_y < 0 || new_y >= grid[0].size()) {

            return false;

        }

        return true;

    }

    int orangesRotting(vector<vector<int>>& grid) {

        int fresh_count = 0;

        queue<pair<int,int>> q;

        int rows = grid.size();

        if (rows == 0) {

            return 0;

        }

        int cols = grid[0].size();

        for (int i = 0; i < rows; i++) {

            for (int j = 0; j < cols; j++) {

                if (grid[i][j] == 1) {

                    fresh_count++;

                } else if (grid[i][j] == 2) {

                    q.push({i, j});

                }

            }

        }

        

        vector<vector<bool>> visited(rows, vector<bool>(cols, false));

        vector<vector<int>> neighbors = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        int ans = 0;

        int rotten = 0;

        while (!q.empty()) {

            int size = q.size();

            if (size == 0) {

                break;

            }

            for (int i = 0; i < size; i++) {

                pair<int, int> rotten_node = q.front(); q.pop();

                for (auto neighbor : neighbors) {

                    int new_x = rotten_node.first + neighbor[0];

                    int new_y = rotten_node.second + neighbor[1];

                    if (valid(grid, new_x, new_y) && !visited[new_x][new_y] &&

                       grid[new_x][new_y] == 1) {

                        rotten++;

                        grid[new_x][new_y] = 2;

                        q.push({new_x, new_y});

                        visited[new_x][new_y] = true;

                    }

                }

            }

            ans++;

        }

        if (rotten == fresh_count) {

            return ans != 0 ? ans - 1 : 0;

        }

        return -1;

    }

};

Reverse doubly linked list (recursive)

#include <iostream>

using namespace std;

class node {

public:

    int val;

    node *next;

    node *prev;

    node(int val_) {

        val = val_;

        next = NULL;

        prev = NULL;

    }

};

void print(node *head) {

    while (head != NULL) {

        cout << head -> val << "<=>";

        head = head -> next;

    }

    cout << endl;

}

node * create() {

    node *head = NULL;

    node *iter = head;

    for (int i = 1; i <= 6; i++) {

        if (i == 1) {

            head = new node(i);

            iter = head;

        } else {

            iter -> next = new node(i);

            iter -> next -> prev = iter;

            iter = iter -> next;

        }

    }

    return head;

}

// NULL<-1<->2<->3<->4<->5<->6->NULL

// 1 -> right = 2            // 1 -> right = NULL

// 1 -> left = NULL          // 1 -> left = 2

// 2 -> left = 1             // 2 -> right = 1

// 2 -> right = NULL         // 2 -> left = NULL

// 1 2 3 4 5 6

// 6 5 4 3 2 1

node *reverse(node* head, node*& new_head) {

    if (head == NULL || head -> next == NULL) {

        if (new_head == NULL) {

            new_head = head;

        }

        return head;

    }

    

    node* returned_node = reverse(head -> next, new_head);

    returned_node -> next = head;

    head -> prev = returned_node;

    return head;

}

int main()

{

    node *head = create();

    print(head);

    

    node *new_head = NULL;

    node *head_ret = reverse(head, new_head);

    new_head -> prev = NULL;

    head_ret -> next = NULL;

    print(new_head);

    

    return 0;

}

328. Odd Even Linked List

 Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

 

Constraints:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on ...
• The length of the linked list is between [0, 10^4]

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode() : val(0), next(nullptr) {}

 *     ListNode(int x) : val(x), next(nullptr) {}

 *     ListNode(int x, ListNode *next) : val(x), next(next) {}

 * };

 */

class Solution {

public:

    ListNode* oddEvenList(ListNode* head) {

        if (head == NULL || head -> next == NULL || head -> next -> next == NULL) {

            return head;

        }

        

        ListNode *oddHead = head;

        ListNode *evenHead = head -> next;

        

        ListNode *oddHeadIter = oddHead, *evenHeadIter = evenHead, *iter = evenHead -> next;

        int count = 1;

        while (iter != NULL) {

            if (count % 2 == 1) {

                evenHeadIter -> next = NULL;

                oddHeadIter -> next = iter;

                oddHeadIter = oddHeadIter -> next;

            } else {

                oddHeadIter -> next = NULL;

                evenHeadIter -> next = iter;

                evenHeadIter = evenHeadIter -> next;

            }

            iter = iter -> next;

            count++;

        }

        oddHeadIter -> next = evenHead;

        return oddHead;

    }

};

974. Subarray Sums Divisible by K

 Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

 

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

 

Note:

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

Approach 1: Prefix Sums and Counting

Intuition

As is typical with problems involving subarrays, we use prefix sums to add each subarray. Let P[i+1] = A[0] + A[1] + ... + A[i]. Then, each subarray can be written as P[j] - P[i](for j > i). Thus, we have P[j] - P[i] equal to 0 modulo K, or equivalently P[i] and P[j] are the same value modulo K.

Algorithm

Count all the P[i]'s modulo K. Let's say there are $C_x$ values $P[i] \equiv x \pmod{K}$. Then, there are $\sum_x \binom{C_x}{2}$ possible subarrays.

For example, take A = [4,5,0,-2,-3,1] and K = 5. Then P = [0,4,9,9,7,4,5], and $C_0 = 2, C_2 = 1, C_4 = 4$:

• With $C_0 = 2$ (at $P[0]$, $P[6]$), it indicates $\binom{2}{2} = 1$ subarray with sum divisible by $K$, namely $A[0:6] = [4, 5, 0, -2, -3, 1]$.
• With $C_4 = 4$ (at $P[1]$, $P[2]$, $P[3]$, $P[5]$), it indicates $\binom{4}{2} = 6$ subarrays with sum divisible by $K$, namely $A[1:2]$, $A[1:3]$, $A[1:5]$, $A[2:3]$, $A[2:5]$, $A[3:5]$.

class Solution {

    public int subarraysDivByK(int[] A, int K) {

        int N = A.length;

        int[] P = new int[N+1];

        for (int i = 0; i < N; ++i)

            P[i+1] = P[i] + A[i];

        int[] count = new int[K];

        for (int x: P)

            count[(x % K + K) % K]++;

        int ans = 0;

        for (int v: count)

            ans += v * (v - 1) / 2;

        return ans;

    }

}

Complexity Analysis

• Time Complexity: $O(N)$, where $N$ is the length of A.

• Space Complexity: $O(N)$. (However, the solution can be modified to use $O(K)$ space by storing only count.)