Rabin-Karp Algorithm – Revisited

In this post we will revisit the implementation of a string-search algorithm developed by Richard Karp and Michael Rabin.

We visited this algorithm in this blog a few years ago. My motivation is a book that I am currently reading. As soon as I am done reading and experimenting with some more advanced algorithms, I will generate several posts associated with the book.

In the meantime, let’s refresh what the Rabin-Karp algorithm is used for and go over an implementation using the Java programming language. Continue reading “Rabin-Karp Algorithm – Revisited”

Bubble Sort in Java

It has been a few weeks since my last post. I apologize for this. Will let you know after my current quest is completed. Hopefully everything will turn out as I desire.

In the meantime I have been taking a few on-line courses.

I am almost done with the course C++20 Fundamentals by Paul J. Deitel. The course was released July, 2021 and published by Pearson3. The ISBN: 013687518. This online course is made available through O’Reilly. I am a member of the Association of Computing Machinery and have access to several O’Reilly titles. Continue reading “Bubble Sort in Java”

Largest Triple Product Third Post in Java

In this post we will revisit a practice question Largest Triple Products. Not sure if today this question would be of interest to Facebook and /or to Meta Platforms technical job seekers.

My original post Largest Triple Products was superseded by Largest Triple Products – Revisited and by this latest post.

The motivation for this post came from a question left by Brent Boyer which suggested an implementation for the function of interest. I have included it in this post as `findMaxProduct3`. Continue reading “Largest Triple Product Third Post in Java”

LeetCode 111. Minimum Depth of Binary Tree in Java

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.

Constraints:

o The number of nodes in the tree is in the range [0, 10^5].
o -1000 <= Node.val <= 1000

Related Topics:

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

LeetCode 295. Find Median from Data Stream in Java

In this post we will try to solve the LeetCode 295. Find Median from Data Stream problem using the Java programming language and the VSCode IDE on a Windows computer.

The median is the middle value in an ordered integer list. 
If the size of the list is even, 
there is no middle value and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

o MedianFinder()
	initializes the MedianFinder object.
o void addNum(int num)
	adds the integer num from the data stream to the data structure.
o double findMedian()
	returns the median of all elements so far. 
	Answers within 10-5 of the actual answer will be accepted.
	
Constraints:

o -10^5 &lt;= num &lt;= 10^5
o There will be at least one element in the data structure before calling findMedian.
o At most 5 * 10^4 calls will be made to addNum and findMedian.

Related Topics:

o Two Pointers
o Design
o Sorting
* Heap (Priority Queue)
o Data Stream

In a nutshell the class needs to process integers in the specified range and at different points we can be asked to return the current Median. As a brute force approach, I tried sorting. I did not submit such an approach because it is quite expensive (slow) and the problem is rated Hard by LeetCode. Continue reading “LeetCode 295. Find Median from Data Stream in Java”

HackerRank Largest Permutation 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.

Constraints

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”

LeetCode 307. Range Sum Query – Mutable in Java

In this post we will tackle the LeetCode 307. Range Sum Query – Mutable problem using the Java programming language and the VSCode IDE on a Windows computer. Unless you have a good reason (i.e., keep test code and solution on the same source code) my suggestion is to solve the problem using the online IDE provided by LeetCode.

Given an integer array nums, handle multiple queries of the following types:

o Update the value of an element in nums.
o Calculate the sum of the elements of nums between indices left and right inclusive 
  where left <= right.

Implement the NumArray class:

o NumArray(int[] nums)
	Initializes the object with the integer array nums.
	
o void update(int index, int val)
	Updates the value of nums[index] to be val.
	
o int sumRange(int left, int right) 
	Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
	
Constraints:

o 1 <= nums.length <= 3 * 10^4
o -100 <= nums[i] <= 100
o 0 <= index < nums.length
o -100 <= val <= 100
o 0 <= left <= right < nums.length
o At most 3 * 10^4 calls will be made to update and sumRange.

Related Topics:

* Array
o Design
o Binary Indexed Tree
* Segment Tree

We are given an int[] and asked to perform two operations as part of a class. Continue reading “LeetCode 307. Range Sum Query – Mutable in Java”

LeetCode 1504. Count Submatrices With All Ones in Java

In this post we will solve LeetCode 1504. Count Submatrices With All Ones problem using the Java programming language, the VSCode IDE on a Windows computer. My suggestion to you is that unless you have some special set of requirements, use the online IDE provided by LeetCode.

Given an m x n binary matrix mat, 
eturn the number of submatrices that have all ones.

Constraints:

o 1 <= m, n <= 150
o mat[i][j] is either 0 or 1.

Related Topics:

o Array
* Dynamic Programming
o Stack
o Matrix
o Monotonic Stack

In this problem we are provided a two dimensional matrix that only contains 1s and 0s. The dimensions are specified by `n` and `m`. Our mission if we wish to accept it, is to return the number of submatrices of 1s. Continue reading “LeetCode 1504. Count Submatrices With All Ones in Java”

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”