Tag: arrays

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”

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 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 242 Valid Anagram in Java

In this post we will be solving the LeetCode 242 Valid Anagram problem using the Java programming language.

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Constraints:

o 1 <= s.length, t.length <= 5 * 10^4
o s and t consist of lowercase English letters.

Related Topics:

o Hash Table
o String
o Sorting

We are given two strings. We need to determine if one string is the anagram of the other. Continue reading “LeetCode 242 Valid Anagram in Java”

LeetCode 872. Leaf-Similar Trees in Java

In this post we will be solving LeetCode 872. Leaf-Similar Trees. As usual, if interested, please visit the LeetCode site and read the current version of the problem to make sure all is well before you start developing code.

Consider all the leaves of a binary tree, 
from left to right order, 
the values of those leaves form a leaf value sequence.

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Constraints:

o The number of nodes in each tree will be in the range [1, 200].
o Both of the given trees will have values in the range [0, 200].

Related Topics:

o Tree
o Depth-First Search
o Binary Tree

We are given two binary trees. We need to determine if the sequence of leaf nodes match or not. Seems like an in-order tree traversal problem. We could populate a list with the leaf nodes of the first tree and repeat with the nodes of the second tree. Our answer will be based on the contents of both lists. Continue reading “LeetCode 872. Leaf-Similar Trees in Java”

Sum of Nodes Between Two Nodes in Binary Tree

Good day!!! Hope all is going well for you. It is Friday and has been a very stressful week for me. Glad that the weekend is just around the corner.

Today we are going to cover a problem which a software engineer and I discussed earlier this week, but for some reason or the other, we did not generate code at the time. We just talked about it.

We are given a binary tree with integer values and two different nodes in the binary tree,
we must return the sum of the values of the nodes that connect p and q inclusive.

Constraints:

o -1000 &lt;= val &lt;= 1000
o 2 &lt;= n &lt;= 200

As you can see, we are given a binary tree populated with integers. Do not recall if all integers were included. We will assume, since I am writing the requirements as we speak, that the values for the nodes are in the specified range and the number of nodes in the binary tree should not exceed the specified value. Continue reading “Sum of Nodes Between Two Nodes in Binary Tree”

Slow Sum – Revisited

Good morning. I received a comment from Dmytro regarding the post Slow Sum suggesting the use of a priority queue instead of a stream. I appreciate the comment and suggestion. Continue reading “Slow Sum – Revisited”

MaxProductOfThree

Good morning! Hope your day has started on the right note.

In this post we will attempt to solve the Codility_ problem MaxProductOfThree using the Java programming language and the VSCode IDE on a Windows platform. We will not be using the online IDE provided by Codility_ since we will write the code on a separate computer. Continue reading “MaxProductOfThree”

High Point in Array

Good morning! It is Friday and the weekend is just around the corner. In the Twin Cities of Minneapolis and St. Paul we received our first snow dusting of the season. Yesterday early morning I drove my wife to a healthcare facility to get a radiological exam. Traffic was heavier than what we expected. We got back home around 09:00 AM. The rest of the day ended for me at 19:00 PM. It was a very long and exciting day.

As the weather changes, I have slightly modified my workdays. I work in 2-hour blocks. The blocks are dictated by the EyeDefender app. I tend to work four to five blocks during the week and one to two on weekends. After each block I get on a stationary bike and pedal backwards for about two minutes and forward for six. This gives me over half an hour of exercise per day and half on weekends.

Starting this week, I will not stop immediately after EyeDefender tells me to do so. Will continue with the bike exercise after each block. Doing this will reduce the blocks to four on workdays. I guess it is better to continue working past the two hours until I reach a normal breaking point based on the task at hand. Will let you know my findings as far as productivity is related early next year.

One last thing, most of the times that I generate a post, I check on the number of subscribers. Today’s count is 10,025 subscribers Thanks a lot!!! This implies that in the very near future I will, in addition to this post, start a YouTube channel with similar content or will just switch to YouTube and discontinue this blog. One way or the other, I will be getting the necessary video hardware and software tools, and will start experimenting with them. I am planning on having the YouTube channel up and running by January 2022. Continue reading “High Point in Array”

Permutation in String

Good morning! Hope you had a nice weekend. My wife and I did. We did some shopping, visited our son, and baked. For some reason last winter we did little baking. Yesterday morning after completing a two-hour block in my home office, I went up, prepared coffee and sat with my wife to chat. The subject of baking came up. Baking is both knowledge and art. In general when cooking or baking we tend not to follow recipes. Yesterday we collected the ingredients for raisin cinnamon bread around 09:00 AM. I got the dough ready around 10:00 AM. The dough proofed for a few hours and early afternoon, while my wife was preparing an avocado with tomatoes and roast beef salad, I buttered four bread molds, poured in the bread batter, waited for about 15 minutes (should be  an hour), and baked the cinnamon raisin bread. It turned out very good, but next week, I will let the bread proof for an hour in the molds. While the bread was still hot, we had two slices each with soft butter and grape jelly made by our daughter in law. It was delicious and to be honest with you, it does not require much work. Continue reading “Permutation in String”