7 Java Intermediate Level Arrays Interview Questions & Answers
Below is a list of our Java Intermediate Level Arrays interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.
1. Can you implement a class SubRectangle?
This interview question concentrates on using Java updates.
Your task is to implement a class SubRectangle. The constructor takes a 2-D matrix of size n X m and stores it. There are two methods in the class:- updateSubrectangle and getValue.
â— The updateSubrectangle updates a portion of the store 2-D matrix with value newValue of the subrectangle whose top-left corner is (row1, col1) and bottom-right corner is (row2, col2).
â— The method getValue returns the value at the provided location.
/*Example*/
passed matrix to the constructor-
[[1, 2, 1],
[4, 3, 4],
[3, 2, 1],
[1, 1, 1]]
the calls made:
1. getValue(0, 2) // returns 1
2. updateSubRectangle(0, 0, 3, 2, 5) // the array becomes:-
[[5, 5, 5],
[5, 5, 5],
[5, 5, 5],
[5, 5, 5]]
3. getValue(0, 2) // returns 5
4. getValue(3, 1) // returns 5
5. updateSubRectangle(3, 0, 3, 2, 10) // the array becomes:-
[[5, 5, 5],
[5, 5, 5],
[5, 5, 5],
[10, 10, 10]]
6. getValue(3, 1) // returns 10
7. getValue(0, 2) // returns 5
class SubrectangleQueries {
public SubrectangleQueries(int[][] rectangle) {
}
public void updateSubrectangle(int row1, int col1, int row2,
int col2, int newValue) {
}
public int getValue(int row, int col) {
}
}
/**
* Your SubrectangleQueries object will be instantiated and called as such:
* SubrectangleQueries obj = new SubrectangleQueries(rectangle);
* obj.updateSubrectangle(row1,col1,row2,col2,newValue);
* int param_2 = obj.getValue(row,col);
*/
Solution:
Approach I (actual update):
After each update call, we will update the given matrix within the passed coordinates of the rectangle. While querying, we directly return the value at passed coordinates.
class SubrectangleQueries {
private int rect[][];
public SubrectangleQueries(int[][] rectangle) {
rect = rectangle;
}
public void updateSubrectangle(int row1, int col1, int row2,
int col2, int newValue) {
for (int i = row1; i <= row2; i++) {
for (int j = col1; j <= col2; j++) {
rect[i][j] = newValue;
}
}
}
public int getValue(int row, int col) {
return rect[row][col];
}
}
Time complexity of updateSubRectangle- O(m * n)
Space complexity of updateSubRectangle- O(1)
Time complexity of getValue O(1)
Space complexity of getValue O(1)
Approach II (lazy update):
In this approach, we will not update the rectangle matrix. Instead we will store the update history:- all the arguments passed to updateSubRectangle will be pushed to this.history as a new array. So the value of this.history after the two calls updateSubRectangle(0, 0, 3, 2, 5) and updateSubRectangle(3, 0, 3, 2, 10) of the example will be:-
this.history = [
[0, 0, 3, 2, 5],
[3, 0, 3, 2, 10]
]
Then during getValue, we will check the most recent update to the value at that coordinates. We will check from the last update to the earliest update i.e. loop in reverse direction on the history array. As soon as we find an update, we will return its value. But, if we don’t find any update in the history array, i.e. it is not updated by any operation, we return the original value this.rectangle[row][col].
class SubrectangleQueries {
private int rect[][];
ArrayList<int[]> history;
public SubrectangleQueries(int[][] rectangle) {
rect = rectangle;
history = new ArrayList<int[]>();
}
public void updateSubrectangle(int row1, int col1, int row2,
int col2, int newValue) {
history.add(new int[]{row1, col1, row2, col2, newValue});
}
public int getValue(int row, int col) {
for (int i = history.size() - 1; i >= 0; i--) {
int history[] = this.history.get(i);
boolean isUpdated =
history[0] <= row &&
row <= history[2] &&
history[1] <= col &&
col <= history[3];
if (isUpdated) {
return history[4];
}
}
return rect[row][col];
}
}
Time complexity of updateSubRectangle- O(1)
Space complexity of updateSubRectangle- O(1)
Time complexity of getValue- O(size of history)
Space complexity of getValue- O(1)
Written by S. Kumar on June 27th, 2021
2. Using the minimum number of operations, move all balls to the ith box.
This interview question concentrates on using Java operations within arrays.
There are n boxes. You are given binary string boxes of length n. If boxes[i] is “1â€, it means the ith box contains 1 ball, and If boxes[i] is “0â€, it means the ith box does not contain any ball.
In one operation, you can move a ball from one box to one of its adjacent boxes. So if the ball is currently in the ith box, you can move it to either (i + 1)st box or (i - 1)st box. Note that, after doing so, some boxes may have more than 1 ball.
Return an array result of size n, where result[i] is the minimum number of operations required to move all the balls to the ith box.
/*Example*/
boxes = "110"
expected output = [1, 1, 3]
0th box:- one operation needed to move the ball from the second box.
1st box:- one operation needed to move the ball from the first box.
2nd box:- two operations needed to move the ball from the first box, and one operation needed to move the ball from the second box.
boxes = "001011"
expected output = [11, 8, 5, 4, 3, 4]
Solution:
We can do it in two passes.
â— In the first pass, for the ith box, we calculate the number of operations required to move all the balls from boxes left of the ith box.
So after the first pass, the result array for example 2 will be:-
[0, 0, 0, 1, 2, 4]
The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes that are on the left side of the ith box.
â— In the second pass, for the ith box, we calculate the number of operations required to move all the balls from boxes right of the ith box. We add the number of operations for the ith box to ith element of the result array obtained after the first pass.
So after the second pass, the result array for example 2 will be:-
[11, 8, 5, 3, 1, 0]
The ith element of the array tells the minimum number of operations to move all the balls to the ith box from all the boxes on both its side.
class Solution {
public int[] minOperations(String boxes) {
int n = boxes.length();
int result[] = new int[n];
Arrays.fill(result, 0);
int ballsCount = 0;
int operationsCount = 0;
for (int i = 0; i < n; i++) {
result[i] += operationsCount;
if (boxes.charAt(i) == '1') ballsCount++;
operationsCount += ballsCount;
}
ballsCount = 0;
operationsCount = 0;
for (int i = n - 1; i >= 0; i--) {
result[i] += operationsCount;
if (boxes.charAt(i) == '1') ballsCount++;
operationsCount += ballsCount;
}
return result;
}
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021
3. Find the winner of an array game.
This question tests the developer's skills working with Java arrays.
You are given an array arr of distinct integers. You are also given an integer k.
In each round, the first element arr[0] and the second element arr[1] play a game. The larger integer wins. It remains at position arr[0] and the smaller number is moved to the end of the array. The game ends when an integer wins k consecutive rounds.
/*Example*/
Given: arr = [2, 1, 3, 5, 4, 6, 7] k = 2
Expected output: 5
Explanation:
Round arr winner win count
1 [2, 1, 3, 5, 4, 6, 7] 2 1
1 [2, 3, 5, 4, 6, 7, 1] 3 1
1 [3, 5, 4, 6, 7, 1, 2] 5 1
1 [5, 4, 6, 7, 1, 2, 3] 5 2
So four rounds are played and 5 wins 2 consecutive games.
Solution:
We will do one pass over the array. We will keep track of the current winner in the variable currWinner. Initially, we are assuming that the first element is the winner. And then we compare currWinner with other numbers in the array one by one. If the element is smaller than currWinner, we increment the variable winCount by 1 which shows the consecutive wins for currWinner. And if the element is greater than currWinner, it means we have a new winner. So update currWinner and start keeping track of its consecutive wins in the variable currWinner. As soon as we find currWinner with winCount equal to k, we break the loop and return currWinner.
There may be a case when we have iterated over all the elements and still didn’t find the currWinner (for example if k > n). For this, we need to focus on one observation. Let len be the length of the array and max be the maximum element in the array. It can be observed that after len - 1 rounds, always max will be the winner because it will be index 0 and no one will be able to beat it. Thus whatever the value of k is, we will return the maximum element in the array. currWinner will hold the maximum element after the loop finishes.
class Solution {
public int getWinner(int[] arr, int k) {
int currWinner = arr[0];
int winCount = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] > currWinner) {
currWinner = arr[i];
winCount = 0;
}
winCount++;
if (winCount == k) break;
}
return currWinner;
}
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021
4. Sort the arrays in colors.
This interview question shows the developer's ability to work with Java partitioning and arrays.
You are given array nums of size n. The array contains only three integers: 0, 1, and 2 representing colors red, white, and blue respectively. Your task is to sort the array in place so that all the same integers are grouped together with colors in order red, white, and blue.
/*Example*/
Given nums = [2 ,0, 2, 1, 1, 0]
Expected output: [0 ,0, 1, 1, 2, 2]
Given nums = [2, 0, 1]
Expected output:- [0, 1, 2]
Solution:
Approach I (counting colors):
In this approach, first, we will count each color in the array. After counting, we will overwrite those colors in the array nums starting with red(0), then white(0), and then blue(2).
class Solution {
public void sortColors(int[] nums) {
int counts[] = {0, 0, 0};
for (int num : nums) {
counts[num]++;
}
for (int i = 0; i < nums.length; i++) {
if (counts[0] != 0) nums[i] = 0;
else if (counts[1] != 0) nums[i] = 1;
else nums[i] = 2;
counts[nums[i]]--;
}
}
}
Time complexity- O(n)
Space complexity- O(1)
Approach II (three-way partitioning):
This is a Dutch national flag problem. We have three types of numbers:- red, white, and blue. We want to group the similar ones and sort the groups in order: red, white, and blue. Let’s call these groups as redGroup, whiteGroup and blueGroup. We will have three-pointers (indices) to the nums array:
1. redIdx: it points to the right end of redGroup (exclusive)
2. whiteIdx: it points to the right end of whiteGroup (exclusive)
3. blueIdx: it points to the left end of blueGroup (exclusive)
For example, in the final sorted array: the pointers are:-
0 0 0 1 1 1 2 2 2
| | |
redIdx blueIdx whiteIdx
While the array is not completely sorted, these indexes convey the following information:
1. redIdx: points to where the next red color will be inserted
2. whiteIdx: points to where the next white color will be inserted
3. blueIdx: points to where the next blue color will be inserted
We will iterate over the array. In iteration, we check the color at index whiteIdx. If it is
1. red, we swap numbers at whiteIdx and redIdx, effectively inserting red color at redIdx,
2. white, we just increment whiteIdx by 1, effectively inserting white color at the previous value of whiteIdx,
3. blue, we swap numbers at whiteIdx and blueIdx, effectively inserting blue color at blueIdx.
Let’s take example of [2 ,0, 2, 1, 1, 0]
----------------------------------------------------------------------
Before iteration:
2 0 2 1 1 0
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 1:
0 0 2 1 1 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 2:
0 0 2 1 1 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 3:
0 0 2 1 1 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 4:
0 0 1 1 2 2
| |
redIdx and whiteIdx blueIdx
----------------------------------------------------------------------
After iteration 5:
0 0 1 1 2 2
| |
redIdx whiteIdx and blueIdx
----------------------------------------------------------------------
After iteration 5:
0 0 1 1 2 2
| | |
redIdx blueIdx whiteIdx
----------------------------------------------------------------------
whiteIdx and blueIdx cross each other, so we break the loop. And the array is sorted!
class Solution {
public void sortColors(int[] nums) {
int redIdx = 0;
int whiteIdx = 0;
int blueIdx = nums.length - 1;
while(whiteIdx <= blueIdx) {
if (nums[whiteIdx] == 0) {
swapIndex(nums, redIdx, whiteIdx);
redIdx++;
whiteIdx++;
} else if (nums[whiteIdx] == 1) {
whiteIdx++;
} else {
swapIndex(nums, blueIdx, whiteIdx);
blueIdx--;
}
}
}
private void swapIndex(int[] nums, int idx1, int idx2) {
int temp = nums[idx1];
nums[idx1] = nums[idx2];
nums[idx2] = temp;
}
}
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on June 27th, 2021
5. What is the max height increase to keep the city skyline?
This question shows the developer's ability to work with Java iteration and arrays.
You are in a beautiful city. The city contains many buildings in the 2-D plane. The city is represented by a 2-D matrix grid. grid[i][j] represents the height of the building at the location. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.
Your task is to increase the heights of the buildings in such a way that the skylines of the city in all four directions remain the same as the skyline of the city represented by the original grid. Return the maximum total sum of the increased heights.
/*Example*/
Given grid = [
[3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0],
]
Expected output: 35
Explanation:
The skyline of original from top or bottom: [9, 4, 8, 7]
The skyline of original from left or right: [8, 7, 9, 3]
The grid after increasing heights maximally without affecting skylines:-[
[8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3],
]
The total increase in heights = 35
Note that the skylines remain the same in all directions. If we increase the height of even one building even by one unit, the skylines will be changed.
Solution:
First of all, we will find the skylines of the city. To store the skylines, we use two arrays leftRightSkyline and topBottomSkyline for left-right and top-bottom skylines respectively. Then we iterate over the whole grid and find the skylines.
â— For each row, the max height in that row will be the skyline for that row when viewed from left or right.
â— For each column, the height in that row will be the skyline for that row when viewed from left or right.
[
[3, 0, 8, 4], -> max = 8 (these are row max or left-right skyline)
[2, 4, 5, 7], -> max = 7
[9, 2, 6, 3], -> max = 9
[0, 3, 1, 0], -> max = 3
| | | |
9 4 8 7
(these are column max or top-bottom skyline)
]
After finding the skylines, we try to find the change in heights for each building such that it does not change the skylines. For this, we iterate over the whole grid again. For each building, we know its row and column, and the max heights in those rows and columns.
Let’s say the building is at coordinate i and j with row max = row_max_i = leftRightSkyline[i] and column max column_max_j = topBottomSkyline[j]
Let originalHeight be the original height of the building, that is, originalHeight = grid[i][j]
Let finalHeight be the height of the building after the increase in height
Now assume row_max_i > column_max_j, and we change finalHeight to row_max_i. In this case, the skyline for that column will be changed. But if we change finalHeight to column_max_j, the skyline both in the row and the column will remain unchanged. Thus finalHeight will be the minimum of row_max_i and column_max_j or
finalHeight = minOf(row_max_i, column_max_j)
The increase in the height will be finalHeight - originalHeight. We will sum over these increases into ans and return it.
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int rowCount = grid.length;
int columnCount = grid[0].length;
int leftRightSkyline[] = new int[rowCount];
int topBottomSkyline[] = new int[columnCount];
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
leftRightSkyline[i] = Math.max(
leftRightSkyline[i],
grid[i][j]
);
topBottomSkyline[j] = Math.max(
topBottomSkyline[j],
grid[i][j]
);
}
}
int ans = 0;
for (int i = 0; i < rowCount; i++) {
for (int j = 0; j < columnCount; j++) {
int originalHeight = grid[i][j];
int finalHeight = Math.min(
leftRightSkyline[i],
topBottomSkyline[j]
);
int increasedHeight = finalHeight - originalHeight;
ans += increasedHeight;
}
}
return ans;
}
}
n = number of rows in grid
m = number of columns in grid
Time complexity- O(n * m)
Space complexity- O(n + m)
Written by S. Kumar on June 27th, 2021
6. Return the number of battleships on the board.
This question focuses on Java cells and iteration.
You are given the n x m matrix board. Each cell is either “X†or empty “.â€. The “X†in a cell represents a part of a battleship. Your task is to return the number of battleships on the board.
A battleship can be either horizontal or vertical. In other words, a battleship of size k is either of shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column). There are no adjacent battleships i.e., at least one horizontal or vertical cell separates any two battleships.
/*Example*/
Given board = [
["X", ".", ".", "X"],
[".", ".", ".", "X"],
[".", ".", ".", "X"],
[".", ".", ".", "."],
]
Expected output: 2
Explanation: There are two battleships. One of size 1 at coordinates (0, 0). The other is of size 3 at coordinates (0, 3), (1, 3), and (2, 3).
Solution:
Since there are no two adjacent battleships, the top and right cells to the top-left of a battleship are empty. For example,
[
["X", ".", ".", "."],
[".", "X", "X", "."],
[".", ".", ".", "X"],
[".", ".", ".", "X"],
]
In the above example, the top-left coordinate of the ship {(1, 1), (1, 2)} is (1, 1). The top and right cells to this cell are (0, 1) and (1, 0) both of which are empty. This will be true for all battleships.
We will iterate over the whole matrix and will find such top-left cells of the battleships. The count of these cells will be equal to the number of battleships present on the board.
class Solution {
public int countBattleships(char[][] board) {
int rowsCount = board.length;
int colsCount = board[0].length;
int count = 0;
for (int i = 0; i < rowsCount; i++) {
for (int j = 0; j < colsCount; j++) {
if (board[i][j] == '.') continue;
if (i > 0 && board[i - 1][j] == 'X') continue;
if (j > 0 && board[i][j - 1] == 'X') continue;
// (i, j) is the top-left part of the ship
count++;
}
}
return count;
}
}
n = number of nodes in the tree
Time complexity- O(n)
Space complexity- O(n)
Written by S. Kumar on June 27th, 2021
7. Return a list of coordinates in a spiral matrix.
This question shows the developer's ability to work with Java loops.
You are given four integers:- rows, cols, rStart, cStart. Imagine a grid of size rows x cols. You are currently at cell (rStart, cStart) (0-indexed) facing east. You walk in a clockwise spiral shape to visit every position of the grid. Whenever you move outside the grid, you continue to walk outside the grid and will return to the grid boundary later. Eventually, all the cells of grids are visited. Your task is to return a list of coordinates of the cells of the grids in the order they were visited.
/*Example*/
Given: rows = 3 cols = 3 rStart = 0 cStart = 1
Expected output: [[0, 1], [0, 2], [1, 2], [1, 1], [1, 0], [0, 0], [2, 2], [2, 1], [2, 0]]
Explanation:
Legends:- > (east) < (west) ^ (north) v (south)
> > > > > > v
6 1 > 2 v
^ v v
5 < 4 < 3 v
v
9 < 8 < 7 < v
After visiting the 6th cell, we go out of the grid, we continue walking in the spiral form outside the grid, and re-enters the grid at cell (2, 2).
Solution:
We will take the walk iteratively starting from the cell (rStart, cStart). If the current cell is not bounded (it does not belong to the grid), we will skip to the next cell. If it is bounded, then we will push it the result array res.
It can be seen that the path is as follows:
move east 1 step, turn right
move south 1 step, turn right
move west 2 steps, turn right
move north 2 steps, turn right
move east 3 steps, turn right
move south 3 steps, turn right
move west 4 steps, turn right
move north 4 steps, turn right
… and so on.
So the number of steps in the directions while taking a walk is a sequence: 1, 1, 2, 2, 3, 3, 4. Let this be stored in the variable stepsCount. We have a variable direction to store our current direction of the walk with values 0, 1, 2, or 3 for east, south, west, or north respectively. The value of stepsCount changes when the new direction is either east or west (0 or 3).
We start our loop with current coordinates rStart and cStart stored in variables x and y. In each iteration, we change the coordinates of the current position using the function changeCell. This function takes the coordinates of the current position and the current direction.
â— If direction is 0 (east), we move position right, that is, (x, y) -> (x, y + 1)
â— If direction is 1 (south), we move position bottom, that is, (x, y) -> (x + 1, y)
â— If direction is 2 (west), we move position left, that is, (x, y) -> (x, y - 1)
â— If direction is 3 (north), we move position top, that is, (x, y) -> (x - 1, y)
Then we check if the newly changed coordinates belong to the grid or not using the function isBounded. In the end, we change direction and increase stepsCount, if required.
class Solution {
public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
int totalCells = rows * cols;
int res[][] = new int[totalCells][2];
int direction = 0;
int stepsCount = 1;
int x = rStart;
int y = cStart;
int pos = 0;
res[pos][0] = x;
res[pos][1] = y;
while(pos < totalCells - 1) {
for (int i = 0; i < stepsCount; i++) {
Pair<Integer, Integer> nextCell =
changeCell(x, y, direction);
x = nextCell.getKey();
y = nextCell.getValue();
if (isBounded(x, y, rows, cols)) {
pos++;
res[pos][0] = x;
res[pos][1] = y;
}
}
direction = (direction + 1) % 4;
if (direction % 2 == 0) stepsCount++;
}
return res;
}
private Pair<Integer, Integer> changeCell(
int x,
int y,
int direction
) {
if (direction == 0) return new Pair(x, y + 1);
if (direction == 1) return new Pair(x + 1, y);
if (direction == 2) return new Pair(x, y - 1);
return new Pair(x - 1, y);
}
private boolean isBounded(int x, int y, int rows, int cols) {
return (
x >= 0 &&
x < rows &&
y >= 0 &&
y < cols
);
}
}
Time complexity- O((max(rows, cols))2)
Auxiliary Space complexity- O(1)
Total Space complexity- O(rows * cols)
Written by S. Kumar on June 27th, 2021