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.)