In this post we will solve LeetCode 111. Minimum Depth of Binary Tree problem using Java and the VSCode IDE on a Windows computer. Not that it matters, but I am using Windows 11.
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path
from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
o The number of nodes in the tree is in the range [0, 10^5].
o -1000 <= Node.val <= 1000
* Depth-First Search
* Breadth-First Search
o Binary Tree
We are given the root of a binary tree and are asked to find the minimum depth of the tree. A couple years ago we solved in this post Maximum Depth of a Binary Tree.
The definition of minimum depth is provided in the requirements for the problem at hand. Continue reading “LeetCode 111. Minimum Depth of Binary Tree in Java”
In this post we will be solving the HackerRank Largest Permutation problem using the Java programming language, the VSCode IDE and a Windows computer.
You are given an unordered array of `unique integers` incrementing from 1.
You can swap any two elements a limited number of times.
Determine the largest lexicographical value array that can be created
by executing `no more` than the limited number of swaps.
o 1 <= n <= 10^5
o 1 <= k <= 10^9
We are given a list of unique integers incrementing from 1. We can swap two values at a time up to a number `k`. We need to return the largest possible permutation in the list. Continue reading “HackerRank Largest Permutation in Java”
In this post we will solve the LeetCode 42. Trapping Rain Water problem using the Java programming language and the VSCode IDE on a Windows computer. The simplest approach is to develop the code on the online IDE provided by LeetCode.
Given n non-negative integers representing an
elevation map where the width of each bar is 1,
compute how much water it can trap after raining.
o n == height.length
o 1 <= n <= 2 * 10^4
o 0 <= height[i] <= 10^5
* Two Pointers
o Dynamic Programming
o Monotonic Stack
The diagram on the LeetCode page is very useful to get the general idea of what the problem is. It also helps to draw the diagram on a piece of paper and figure out an approach. We need to calculate the amount of water on each cell and add them together to get our result. The trick is in how we implement the task. Continue reading “LeetCode 42. Trapping Rain Water in Java”
In this post we will try to define some requirements and then solve the problem. I briefly saw this problem and was not able to get all the details. If it does not make much sense you could specify a variant and go on and solve it.
In this problem we are given a list of offer items and cart items.
The cart items are provided in the order the customer put them in the shopping cart.
The offer items are a list of list of items that must be put into the cart in the order specified.
I guess there could be different versions of the requirements,
but in our case,
we need to make sure that all items in all the item lists are placed in the cart in the specified order.
Perhaps it would be more reasonable to get an additional discount if
a set of items are placed in a specified order in the shopping cart,
or better yet,
if each set of items ends in the shopping cart the customer could receive additional offers.
We need to return true if all items are placed in the shopping cart in the specified order;
otherwise we return false.
o 1 <= number of items <= 100
o 0 <= number of offers <= 100
o The string `anything` in the offers indicates
that the correspoinding item in the shopping cart should be ignored.
The requirements call for having two lists available. In one is a set of offers that require all the specified items to be placed (not just be found) into the cart in the order specified by the offer item. Not only that, but all items must be placed in the cart in the order specified by all offers. That is how we will proceed. Continue reading “Fruit Order in Cart in Java”
In this post we will solve the LeetCode 904. Fruit Into Baskets problem using the Java programming language.
You are visiting a farm that has a single row of fruit trees arranged from left to right.
The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible.
However, the owner has some strict rules that you must follow:
o You only have two baskets, and each basket can only hold a single type of fruit.
There is no limit on the amount of fruit each basket can hold.
o Starting from any tree of your choice,
you must pick exactly one fruit from every tree (including the start tree) while moving to the right.
The picked fruits must fit in one of your baskets.
o Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
o 1 <= fruits.length <= 10^5
o 0 <= fruits[i] < fruits.length
o Hash Table
o Sliding Window
The two approaches that came to mind are using a hashmap, which should not have the best performance but should be acceptable, and the second using a sliding window, which should be faster than the one using a hashmap. Continue reading “LeetCode 904. Fruit Into Baskets in Java”
In this post we will solve the LeetCode 1302. Deepest Leaves Sum problem using the Java programming language with the VSCode IDE on a Windows computer.
Given the root of a binary tree,
return the sum of values of its deepest leaves.
o The number of nodes in the tree is in the range [1, 10^4].
o 1 <= Node.val <= 100
o Depth-First Search
o Breadth-First Search
o Binary Tree
We are given a binary tree and we need to return the sum of the values of all deepest leaves. Continue reading “LeetCode 1302. Deepest Leaves Sum in Java”
In this post we will solve LeetCode 235. Lowest Common Ancestor of a Binary Tree problem using Java.
Given a binary search tree (BST),
find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia:
“The lowest common ancestor is defined between two nodes p and q
as the lowest node in T that has both p and q as descendants
(where we allow a node to be a descendant of itself).”
o The number of nodes in the tree is in the range [2, 10^5].
o -10^9 <= Node.val <= 10^9
o All Node.val are unique.
o p != q
o p and q will exist in the BST.
o Depth-First Search
o Binary Search Tree
o Binary Trea
We are given a Binary Search Tree (BST) and the pointers / references to two nodes in the tree. We need to return the Lowest Common Ancestor (LCA) node. Continue reading “LeetCode 235. Lowest Common Ancestor of a Binary Tree in Java”
In this post we will solve the LeetCode 1156. Swap For Longest Repeated Character Substring problem using the Java programming language.
You are given a string text. You can swap two of the characters in the text.
Return the length of the longest substring with repeated characters.
o 1 <= text.length <= 2 * 10^4
o text consist of lowercase English characters only.
o Sliding Window
We are given a string of English lowercase characters and we can swap two characters once in order to return the longest count of consecutive characters. Continue reading “LeetCode 1156. Swap For Longest Repeated Character Substring in Java”
In this post we will solve the LeetCode 1347 Minimum Number of Steps to Make Two Strings Anagram problem using Java.
You are given two strings of the same length s and t.
In one step you can choose any character of t and replace it with another character.
Return the minimum number of steps to make t an anagram of s.
An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.
o 1 <= s.length <= 5 * 10^4
o s.length == t.length
o s and t consist of lowercase English letters only.
o Hash Table
It seems that in this problem it is needed to replace the minimum number of characters in string `t` with lowercase characters from the English alphabet in order to make `t` an anagram of string `s`. Continue reading “LeetCode 1347 Minimum Number of Steps to Make Two Strings Anagram in Java”
In this post we will solve LeetCode 223 Rectangle Area in Java.
Given the coordinates of two rectilinear rectangles in a 2D plane,
return the total area covered by the two rectangles.
The first rectangle is defined by its bottom-left corner (ax1, ay1) and its top-right corner (ax2, ay2).
The second rectangle is defined by its bottom-left corner (bx1, by1) and its top-right corner (bx2, by2).
o -10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4
We are given the coordinates of two rectilinear rectangles in a 2D plane and are asked to return the total area covered by the two rectangles. Continue reading “LeetCode 223 Rectangle Area in Java”