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 <= num <= 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 1156. Swap For Longest Repeated Character Substring 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.

Constraints:

o 1 <= text.length <= 2 * 10^4
o text consist of lowercase English characters only.

Related Topics:

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

Find Leaf Nodes in a Tree for which the Sum of the Root Path Matches a Target Value

I did not find this problem on a website. The requirements came up during a conversation with a software engineer. I wish I could have taken some notes but I did not. The problem had a single diagram of a sample general tree and there was no class definition for the nodes.

We are given a general binary three in which a node may have none, one or more children.
In addition each node has an integer value.
The values may repeat.

Our tasks if to come up with a function 
that will display the leaf nodes 
for which the sum of all node values in the path from the root 
add up to a defined target.

As far as I can remember that was the gist of the problem. Continue reading “Find Leaf Nodes in a Tree for which the Sum of the Root Path Matches a Target Value”