Last updated on December 21st, 2023
Tracking my daily progress for LeetCode challenges. This is a continuation of this post.
The source code for these examples can be found on the GitHub repo.
Dec 21 2023 – Widest Vertical Area Between Two Points Containing No Points
Difficulty Level: Medium
It should pass below test cases:
class WidestVerticalAreaTest {
public static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(new int[][]{{8, 7}, {9, 9}, {7, 4}, {9, 7}}, 1),
Arguments.of(new int[][]{{3, 1}, {9, 0}, {1, 0}, {1, 4}, {5, 3}, {8, 8}}, 3)
);
}
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void maxWidthOfVerticalAreaTest(int[][] input, int expected) {
assertEquals(expected, WidestVerticalArea.maxWidthOfVerticalArea(input));
}
}
The initial approach is quite simple. I sorted the matrix in ascending order of x-coordinates and then calculated the maximum distance between consecutive x-coordinates. The time complexity is O(n logn).
public static int maxWidthOfVerticalArea(int[][] points) {
int max = 0;
Arrays.sort(points, Comparator.comparingInt(obj -> obj[0]));
for (int i = 0; i < points.length - 1; i++) {
if (points[i + 1][0] - points[i][0] > max) {
max = points[i + 1][0] - points[i][0];
}
}
return max;
}
Dec 20 2023 – Buy Two Chocolates
Difficulty Level: Easy
It should pass below test cases:
class BuyTwoChocolateTest {
public static Stream<Arguments> pricesMoneyExpectedLeftover() {
return Stream.of(
Arguments.of(new int[] {1,2,2}, 3, 0),
Arguments.of(new int[] {3,2,3}, 3, 3)
);
}
@ParameterizedTest
@MethodSource("pricesMoneyExpectedLeftover")
void buyChocoTest(int[] prices, int money, int expectedLeftover) {
assertEquals(expectedLeftover, BuyTwoChocolates.buyChoco(prices, money));
}
}
The initial approach is quite simple. I sorted the array and then calculated the leftovers. The time complexity is O(n logn).
public static int buyChocoBySorted(int[] prices, int money) {
int[] sortedPrices = Arrays.stream(prices).sorted().toArray();
int leftover = money;
if (money >= (sortedPrices[0] + sortedPrices[1])) {
leftover = money - sortedPrices[0] - sortedPrices[1];
}
return leftover;
}
However, we can optimize the time complexity by avoiding sorting the array. We just need to iterate over the prices list, find the minimum chocolate price and the second minimum one, and then calculate the leftovers.
public static int buyChoco(int[] prices, int money) {
int leftover = money;
int min = Integer.MAX_VALUE;
int secondMin = Integer.MAX_VALUE;
for (int price : prices) {
if (price < min) {
secondMin = min;
min = price;
} else if (price < secondMin) {
secondMin = price;
}
}
if (money >= min + secondMin) {
leftover = money - min - secondMin;
}
return leftover;
}
The time complexity now is O(n).
Dec 19 2023 – Image Smoother
Difficulty Level: Easy
It should pass below test cases:
class ImageSmootherTest {
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void isAnagramTest(int[][] input, int[][] expectedOutput) {
assertArrayEquals(expectedOutput, ImageSmoother.imageSmoother(input));
}
public static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(new int[][]{
{1, 1, 1},
{1, 0, 1},
{1, 1, 1},
}, new int[][]{
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
}),
Arguments.of(new int[][]{
{100, 200, 100},
{200, 50, 200},
{100, 200, 100},
}, new int[][]{
{137, 141, 137},
{141, 138, 141},
{137, 141, 137}
})
);
}
}
My solution:
public static int[][] imageSmoother(int[][] img) {
int[][] result = new int[img.length][img[0].length];
for (int i = 0; i < img.length; i++) {
for (int j = 0; j < img[0].length; j++) {
int sum = img[i][j];
int count = 1;
if (i - 1 >= 0) {
sum += img[i - 1][j];
count += 1;
}
if (j - 1 >= 0) {
sum += img[i][j - 1];
count += 1;
}
if (i - 1 >= 0 && j - 1 >= 0) {
sum += img[i - 1][j - 1];
count += 1;
}
if (i - 1 >= 0 && j + 1 < img[0].length) {
sum += img[i - 1][j + 1];
count += 1;
}
if (i + 1 < img.length) {
sum += img[i + 1][j];
count += 1;
}
if (j + 1 < img[0].length) {
sum += img[i][j + 1];
count += 1;
}
if (i + 1 < img.length && j + 1 < img[0].length) {
sum += img[i + 1][j + 1];
count += 1;
}
if (j - 1 >= 0 && i + 1 < img.length) {
sum += img[i + 1][j - 1];
count += 1;
}
result[i][j] = sum / count;
}
}
return result;
}
The time complexity is O(n *m).
Dec 18 2023 – Maximum Product Difference Between Two Pairs
Difficulty Level: Easy
It should pass below test cases:
class DifferencesMaximumTest {
public static Stream<Arguments> inputExpectedMaxDifference() {
return Stream.of(
Arguments.of(new int[]{5, 6, 2, 7, 4}, 34),
Arguments.of(new int[]{2, 9, 5, 9, 1}, 79),
Arguments.of(new int[]{1, 6, 7, 5, 2, 4, 10, 6, 4}, 68),
Arguments.of(new int[]{10, 10, 10, 10}, 0),
Arguments.of(new int[]{4, 2, 5, 9, 7, 4, 8}, 64)
);
}
@ParameterizedTest
@MethodSource("inputExpectedMaxDifference")
void maxProductDifferenceTest(int[] input, int expected) {
assertEquals(expected, DifferencesMaximum.maxProductDifferenceBySortedApproach(input));
assertEquals(expected, DifferencesMaximum.maxProductDifference(input));
}
}
The initial approach is quite simple. I sorted the array and then calculated the difference between two pairs. The time complexity is O(n logn).
public static int maxProductDifferenceBySortedApproach(int[] nums) {
int[] sortedArr = Arrays.stream(nums).sorted().toArray();
return (sortedArr[sortedArr.length - 1] * sortedArr[sortedArr.length - 2])
- (sortedArr[0] * sortedArr[1]);
}
However, we can optimize the time complexity by not sorting the array, just need to integrate through the list.
public static int maxProductDifference(int[] nums) {
int smallest = Integer.MAX_VALUE;
int minSecond = Integer.MAX_VALUE;
int biggest = 0;
int maxSecond = 0;
for (int num : nums) {
if (num > biggest) {
maxSecond = biggest;
biggest = num;
} else {
if (num > maxSecond) {
maxSecond = num;
}
}
if (num < smallest) {
minSecond = smallest;
smallest = num;
} else {
if (num < minSecond) {
minSecond = num;
}
}
}
return (maxSecond * biggest) - (minSecond * smallest);
}
The time complexity now is O(n).
Dec 14 2023 – Difference Between Ones and Zeros in Row and Column
Difficulty Level: Medium
It should pass below test cases:
class OneAndZeroDifferencesTest {
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void onesMinusZerosTest(int[][] input, int[][] expectedOutput) {
assertArrayEquals(expectedOutput, OnesAndZeros.onesMinusZeros(input));
}
public static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(new int[][]{
{0, 1, 1},
{1, 0, 1},
{0, 0, 1}
}, new int[][]{
{0, 0, 4},
{0, 0, 4},
{-2, -2, 2}
}),
Arguments.of(new int[][]{
{1, 1, 1},
{1, 1, 1}
}, new int[][]{
{5, 5, 5},
{5, 5, 5}
})
);
}
}
My initial approach is quite simple. Just loop through each of element and calculate the corresponding difference between ones and zeros in row and column. The time complexity is O(m*n*(m+n)).
public static int[][] onesMinusZerosO3(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = calculateDifferences(grid, i, j);
}
}
return result;
}
private static int calculateDifferences(int[][] grid, int i, int j) {
int res = 0;
for (int k = 0; k < grid[i].length; k++) {
if (grid[i][k] == 1) {
res += 1;
} else {
res -= 1;
}
}
for (int k = 0; k < grid.length; k++) {
if (grid[k][j] == 1) {
res += 1;
} else {
res -= 1;
}
}
return res;
}
However, we can see that in the above approach, it repeated iteration to compute the total of zeros and ones. This is where we can improve.
public static int[][] onesMinusZeros(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] result = new int[m][n];
// Counting ones and zeros in each row and column
int[] onesRow = new int[m];
int[] onesCol = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
onesRow[i]++;
onesCol[j]++;
} else {
onesRow[i]--;
onesCol[j]--;
}
}
}
// Calculate the difference matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = onesRow[i] + onesCol[j] ;
}
}
return result;
}
This approach will use two arrays to store the total of zeros and ones for row and column. The time complexity now is O(m*n).
Dec 13 2023 – Special Positions in a Binary Matrix
Difficulty Level: Easy
It should pass below test cases:
class BinaryMatrixTest {
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void numSpecialTest(int[][] input, int expectedOutput) {
assertEquals(expectedOutput, BinaryMatrix.numSpecial(input));
}
public static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(new int[][]{
{1, 0, 0},
{0, 0, 1},
{1, 0, 0}
}, 1),
Arguments.of(new int[][]{
{1, 0, 0},
{0, 1, 0},
{0, 0, 1}
}, 3),
Arguments.of(new int[][]{
{0, 1, 0},
{0, 0, 0},
{1, 0, 0},
{1, 0, 0}
}, 1)
);
}
}
My solution:
public static int numSpecial(int[][] matrix) {
int count = 0;
int m = matrix.length;
int n = matrix[0].length;
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
if (matrix[row][col] == 1) {
if (!onlyOneCellOneInRow(matrix, row, col)) {
continue;
}
if (!onlyOneCellOneInCol(matrix, row, col)) {
continue;
}
count++;
}
}
}
return count;
}
// Check if only one cell in the row is 1
private static boolean onlyOneCellOneInRow(int[][] matrix, int row, int col) {
for (int i = 0; i < matrix[row].length; i++) {
if (col != i && (matrix[row][i] == 1)) {
return false;
}
}
return true;
}
// Check if only one cell in the column is 1
private static boolean onlyOneCellOneInCol(int[][] matrix, int row, int col) {
for (int i = 0; i < matrix.length; i++) {
if (i != row && (matrix[i][col] == 1)) {
return false;
}
}
return true;
}
The time complexity is O(m*n*(m+n)).
Dec 12 2023 – Maximum Product of Two Elements in an Array
Difficulty Level: Easy
It should pass below test cases:
class MaxProductTest {
@ParameterizedTest
@MethodSource("inputExpectedOutput")
void maxProductTest(int[] input, int expectedOutput) {
assertEquals(expectedOutput, MaxProduct.maxProduct(input));
}
public static Stream<Arguments> inputExpectedOutput() {
return Stream.of(
Arguments.of(new int[] {3,4,5,2}, 12),
Arguments.of(new int[] {1,5,4,5}, 16),
Arguments.of(new int[] {3, 7}, 12)
);
}
}
My solution:
public static int maxProduct(int[] nums) {
int first = nums[0];
int second = 0;
for (int i=1; i< nums.length; i++) {
if (nums[i] > first) {
second = first;
first = nums[i];
} else {
if (nums[i] > second) {
second = nums[i];
}
}
}
return (first-1) * (second - 1);
}
The time complexity is O(n), where n is the length of the input array.