1. Shift 2D Grid

Although it’s tagged easy, it’s a very good question, to me.

Question:

Given a 2D grid of size n * m and an integer k. You need to shift the grid k times.

In one shift operation:

  • Element at grid[i][j] becomes at grid[i][j + 1].
  • Element at grid[i][m - 1] becomes at grid[i + 1][0].
  • Element at grid[n - 1][m - 1] becomes at grid[0][0].

Return the 2D grid after applying shift operation k times.

Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

Input: grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
Output: [[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

Constraint:

  1. 1 <= grid.length <= 50
  2. 1 <= grid[i].length <= 50
  3. -1000 <= grid[i][j] <= 1000
  4. 0 <= k <= 100
1
2
3
4
5
class Solution {
        public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        
    }
}

Essence: starting from index start = (m * n - k) % (m * n) to m*n + start, create a new list and add to list starting from index 0. Essentially shifting.

Solution:

Java, ArrayList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
        public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length; 
        int start = m * n - k % (m * n);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = start; i < m * n + start; ++i) {
            int j = i % (m * n), r = j / n, c = j % n;
            // same col as start means new row of res
            if ((i - start) % n == 0)
                ans.add(new ArrayList<>());
            ans.get(ans.size()-1).add(grid[r][c]);
        }
        return ans;
    }
}

Java, LinkedList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
        public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length; 
        int start = m * n - k % (m * n);
        // Must specify LinkedList, not just List because only
        // LinkedList has method peekLast, not ArrayList
        LinkedList<List<Integer>> ans = new LinkedList<>();
        for (int i = start; i < m * n + start; ++i) {
            int j = i % (m * n), r = j / n, c = j % n;
            if ((i - start) % n == 0)
                ans.add(new ArrayList<>());
            ans.peekLast().add(grid[r][c]);
        }
        return ans;
    }
}

Additional:

ArrayList:

add, get, indexOf, remove, set, toArray

LinkedList:

add, addFirst, addLast, get, indexOf, offer, peek(retrieve, not remove), peekFirst, peekLast, poll(retrieve, remove), pollFirst, pollLast, remove.

offer, peek, poll: return null if empty; safer than add, get, remove.

Queue
  1. add -> offer,
  2. element -> peek,
  3. remove -> poll

right hand side methods: return null if empty