LeetCode 42. Trapping Rain Water 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.

Constraints:

o n == height.length
o 1 <= n <= 2 * 10^4
o 0 <= height[i] <= 10^5

Related Topics:

* Array
* Two Pointers
o Dynamic Programming
o Stack
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”

LeetCode 681. Next Closest Time in Java

In this post we will solve LeetCode 681. Next Closest Time problem using the Java programming language, the VSCode IDE on a Windows computer. Please note that the computer platform and the IDE should make no difference. One of the simplest ways to solve the problem is to use the online IDE provided by LeetCode.

Given a time represented in the format "HH:MM", 
form the next closest time by reusing the current digits. 
There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. 
For example, "01:34", "12:09" are all valid. 
"1:34", "12:9" are all invalid.

Constraints:

* time.length == 5
* time is a valid time in the form "HH:MM".
o 0 <= HH < 24
o 0 <= MM < 60

Related Topics:

o String
o Enumeration

We are given a string with a time expressed in 24-hour format. By reusing the digits as many times as needed, we need to form the next closest time. Continue reading “LeetCode 681. Next Closest Time in Java”

LeetCode 84. Largest Rectangle in Histogram in Java

In this post we will solve LeetCode 84. Largest Rectangle in Histogram problem using the Java programming language and the VSCode IDE on a Windows computer.

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, 
return the area of the largest rectangle in the histogram.

Constraints:

o 1 <= heights.length <= 10^5
o 0 <= heights[i] <= 10^4

Related Topics:
* Array
o Stack
* Monotonic Stack

We are given an array representing a histogram. The width of each bar holding a value is 1 unit. We are asked to return the area of the largest rectangle in the histogram. Continue reading “LeetCode 84. Largest Rectangle in Histogram in Java”

LeetCode 1804. Implement Trie II (Prefix Tree) in Java

In this post I will solve LeetCode 1804. Implement Trie II (Prefix Tree) problem using Java and the VSCode IDE on a Windows computer.

In a previous post we discussed and implemented a solution for LeetCode 208. Implement Trie (Prefix Tree) in Java which is similar yet different to this one.

Please note that I carried away experimenting with the current problem as I did with the previous one. Due to this I implemented two solutions. After the first one was accepted I tried improving performance and readability. That created a second solution. Due to my approach I ended up with a large amount of code which I will post and comment on. For the first implementation I will go light on comments. Continue reading “LeetCode 1804. Implement Trie II (Prefix Tree) in Java”

LeetCode 208. Implement Trie (Prefix Tree) in Java

In this post I will solve the LeetCode 208 Implement Trie (Prefix Tree) problem using the Java programming language and the VSCode IDE on a Windows computer. After the code was accepted by LeetCode I decided to add a couple features. The first one is to provide a method to access one of the main uses for a Trie (https://en.wikipedia.org/wiki/Trie). The second, which is based on the first one, is used to display, in order, the words inserted into the Trie.

A trie (pronounced as "try") or prefix tree is a tree data structure 
used to efficiently store and retrieve keys in a dataset of strings. 
There are various applications of this data structure, 
such as autocomplete and spellchecker.

Implement the Trie class:

* Trie()
  Initializes the trie object.
* void insert(String word)
  Inserts the string word into the trie.
* boolean search(String word) 
  Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
* boolean startsWith(String prefix) 
  Returns true if there is a previously inserted string word that has the prefix prefix, 
  and false otherwise.
 
Constraints:

o 1 <= word.length, prefix.length <= 2000
o word and prefix consist only of lowercase English letters.
o At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.
 
Related Topics:

o Hash Table
o String
o Design
o Trie

The requirements are very well described. We need to implement the class Trie which must include a specific set of methods. In addition we need to specify the class members. Continue reading “LeetCode 208. Implement Trie (Prefix Tree) in Java”

Fruit Order in Cart 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.

Constraints:
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”

LeetCode 904. Fruit Into Baskets 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.

Constraints:

o 1 <= fruits.length <= 10^5
o 0 <= fruits[i] < fruits.length

Related Topics:

o Array
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”

LeetCode 1302. Deepest Leaves Sum 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.

Constraints:

o The number of nodes in the tree is in the range [1, 10^4].
o 1 <= Node.val <= 100

Related Topics:

o Tree
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”

LeetCode 760. Find Anagram Mappings in Java

In this post we will solve LeetCode 760. Find Anagram Mappings problem using the Java programming language.

You are given two integer arrays nums1 and nums2 where nums2 is an anagram of nums1. 
Both arrays may contain duplicates.

Return an index mapping array mapping from nums1 to nums2 where 
mapping[i] = j means the ith element in nums1 appears in nums2 at index j. 
If there are multiple answers, return any of them.

An array a is an anagram of an array b means b is made by randomizing the order of the elements in a.

Constraints:

o 1 <= nums1.length <= 100
o nums2.length == nums1.length
o 0 <= nums1[i], nums2[i] <= 10^5
o nums2 is an anagram of nums1.

Related Topics:

o Array
o Hash Table

We are provided with two int[] holding two anagrams. We need to write a function that returns an index mapping array mapping from nums1 to nums2 where mapping[i] = j means the ith element in nums1 appears in nums2 at index j. Continue reading “LeetCode 760. Find Anagram Mappings in Java”

LeetCode 235. Lowest Common Ancestor of a Binary Tree 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).”

Constraints:

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.

Realated Topics:

o Tree
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”