Tag: array

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

LeetCode 169 Majority Element in Java

In this post we will attempt to solve LeetCode 169. Majority Element problem using Java.

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than floor(n / 2) times. 
You may assume that the majority element always exists in the array.

Constraints:

o n == nums.length
o 1 <= n <= 5 * 10^4
o -2^31 <= nums[i] <= 2^31 - 1

Related Topics:

o Array
o Hash Table
o Divide and Conquer
o Sorting
o Counting

We are given an int[] array and we must return the majority element. There are several variations of this problem. I believe we have solved a couple in this post. Continue reading “LeetCode 169 Majority Element in Java”

LeetCode 575. Distribute Candies in Java

In this post we will solve the LeetCode 575. Distribute Candies problem.

This problem is not too difficult to get to an answer. Not sure if it was network traffic, but the different attempts, which were accepted, required a different approach. Once you get a first pass accepted, I would suggest that before you leave the LeetCode website, take a look at the implementations that perform best. I was going to implement some of those approaches but got late and had to move on with other tasks.

Alice has n candies, where the ith candy is of type candyType[i]. 
Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). 
Alice likes her candies very much, 
and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, 
return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Constraints:

o n == candyType.length
o 2 <= n <= 10^4
o n is even.
o -10^5 <= candyType[i] <= 10^5

In this problem Alice is given different candies. As we will see in the examples, a type of candy may appear once or more times. Continue reading “LeetCode 575. Distribute Candies in Java”

LeetCode 1185 Day of the Week in Java

In this post we will attempt to solve the LeetCode 1185 Day of the Week problem.

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

In a nutshell we are given a date in day, month, and year and we need to return a string that contains the name of the day. The problem is very easy to understand. Continue reading “LeetCode 1185 Day of the Week in Java”

LeetCode 75. Sort Colors in Java

In this post we will solve the LeetCode 75. Sort Colors problem using the Java programming language and the VSCode IDE on a Windows computer.

Given an array nums with n objects colored red, white, or blue, 
sort them in-place so that objects of the same color are adjacent, 
with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Constraints:

o n == nums.length
o 1 <= n <= 300
o nums[i] is 0, 1, or 2.

We are given an integer array with values 0, 1, and 2 which represent colors red, white and blue respectively. We must solve the problem without the use of any library sort function. That makes sense because we would only have to sort the input array and return. Continue reading “LeetCode 75. Sort Colors in Java”

LeetCode 229. Majority Element II in Java

In this post we will solve the LeetCode 229. Majority Element II problem using two approaches.

Given an integer array of size n, find all elements that appear more than floor(n/3)times.

Constraints:

o 1 <= nums.length <= 5 * 10^4
o -10^9 <= nums[i] <= 10^9

We are given an array of integer values. We need to find all elements whose values are larger than floor(n / 3), where `n` is the number of elements in the input array. Continue reading “LeetCode 229. Majority Element II in Java”

Codility_ problem Fish in Java

In this post we will attempt to solve the Codility_ problem Fish (https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/) in which we are given N voracious fish are moving along a river. Calculate how many fish are alive. Continue reading “Codility_ problem Fish in Java”

Stone Wall

Good day! Hope all is well in your neck of the woods. My wife left lunch in the oven and ran to the dentist office. She left the oven on. Not sure when I should shut it down. I think I will do it right now before the food gets burned. When she gets back we can turn on the oven back if needed.

OK, the oven is off. It is 01:00 PM. I am starving. Hope my wife returns shortly so we can have lunch. Continue reading “Stone Wall”