Tag: two pointers

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 160 Intersection of Two Linked Lists in Java

In this post I will be solving LeetCode 160 Intersection of Two Linked Lists using the Java programming language.

Given the heads of two singly linked-lists headA and headB, 
return the node at which the two lists intersect. 
If the two linked lists have no intersection at all, return null.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

o intersectVal - The value of the node where the intersection occurs.
  This is 0 if there is no intersected node.
o listA - The first linked list.
o listB - The second linked list.
o skipA - The number of nodes to skip ahead in listA (starting from the head) 
  to get to the intersected node.
o skipB - The number of nodes to skip ahead in listB (starting from the head) 
  to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, 
headA and headB to your program.
If you correctly return the intersected node,
then your solution will be accepted.

Constraints:

o The number of nodes of listA is in the m.
o The number of nodes of listB is in the n.
o 1 <= m, n <= 3 * 104
o 1 <= Node.val <= 105
o 0 <= skipA < m
o 0 <= skipB < n
o intersectVal is 0 if listA and listB do not intersect.
o intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Related Topics:

* Hash Table
o Linked List
* Two Pointers

Follow up:

* Could you write a solution that runs in O(m + n) time and use only O(1) memory?

If interested I suggest you get the current description from LeetCode before you start coding. Continue reading “LeetCode 160 Intersection of Two Linked Lists in Java”

LeetCode 141 Linked List Cycle in Java

In this post we will solve the LeetCode 141 Linked List Cycle problem.

Given head, the head of a linked list, 
determine if the linked list has a cycle in it.

There is a cycle in a linked list 
if there is some node in the list that can be reached again by continuously following the next pointer. 

Internally, pos is used to denote the index of the node that tail's next pointer is connected to. 
Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. 
Otherwise, return false.

Constraints:

o The number of the nodes in the list is in the range [0, 10^4].
o -10^5 <= Node.val <= 10^5
o pos is -1 or a valid index in the linked-list.

Related Topics:

o Hash Table
o Linked List
o Two Pointers

We are given a singly linked list and are asked to determine if there is a cycle in it. If interested in the problem please take a look at the current description of it in the LeetCode website. Continue reading “LeetCode 141 Linked List Cycle in Java”

Remove the Nth Node From End of List

Happy Friday! It is a typical fall Friday in the Twin Cities of Minneapolis and St. Paul. When I woke up this morning the outside temperature was 38F. The forecasted high for the day is 56F. Tomorrow the forecasted high temperature will be 67F. Will check with my wife if we will grill outside. Not too many grilling days left this year.

Earlier today I read the article Big whales eat 3 times as much as previously thought, which means killing them for food and blubber is even more harmful to the environment by Marianne Guenot. I also read a different article on the same subject titled The Enormous Hole That Whaling Left Behind by Ed Yong. Both articles are in agreement with the research and published papers. As humans, the idea of fertilizing the waters in specific areas seems to be a good thing to do now that the amounts of iron to use have been accurately estimated. Perhaps in the next few decades the oceans will see whales in the numbers they existed 60 years ago. Continue reading “Remove the Nth Node From End of List”

Middle of the Linked List

I am working on the last 2-hour block of the day. My wife was trying to make a payment for our Internet service, but she needs a number that can only be found in a previous bill receipt. Apparently she can not find one, so at the end of the workday we will go to make a payment in person and will hopefully keep the receipt, so this situation does not repeat. Continue reading “Middle of the Linked List”

Two Sum II

Good morning. Hope you enjoyed the Halloween festivities yesterday. Today is November 01, 2021 and most countries celebrate today “All Saints’ Day” and tomorrow “All Souls’ Day”. In the USA we do not celebrate these holidays.

One way or the other, yesterday shortly past noon the crew of technicians installing our new furnace left, leaving us with an installed, calibrated, and properly functioning furnace. Last night  the low temperature in this part of the Twin Cities of Minneapolis and St. Paul was 30F. The furnace worked a few times at night. It was quieter than our previous unit. What is more important, it worked flawlessly.

Today I have a couple meetings. Besides that it will be a normal workday.

Continue reading “Two Sum II”