Today has been a very busy and stressful day. This morning when I woke up around 06:00 AM I could hear the second zone in the heating system running. That zone includes the lower level at home. While having breakfast it bothered me that the output of the furnace was still sending heat to the second zone. I went down and noticed that the furnace was not working properly. We had an issue last Friday which was fixed Monday afternoon. Apparently the issue was not properly addressed.
I asked my wife to call the company that worked on the furnace. They could not send us a technician today so she called a different company. Hopefully the technician will stop by this afternoon. It is shortly past 05:00 PM and the furnace technician has not arrived. I guess he will be here tomorrow. The good news is that we can keep the house quite warm using the lower level fireplace.
This morning while doing some on-line research, I ran into the Documentation OData 4.0 Java Library. Apache Olingo is a Java library that implements the Open Data Protocol (OData). Apache Olingo serves client and server aspects of OData. It currently supports OData 2.0 and will soon support OData 4.0. The latter is the OASIS version of the protocol: OASIS Open Data Protocol (OData) TC. Planning on experimenting with it in the next few days.
Since a week ago I have been writing this post on Google Docs. When done I save a copy in .docx format on a Windows machine. I used to write posts using Word.
Let’s get down to the main subject of this post.
Earlier today I worked on the next problem in the sequence of algorithms suggested by LeetCode. The problem at hand is LeetCode 977 Squares of a Sorted Array.
Given an integer array nums sorted in non-decreasing (increasing) order, return an array of the squares of each number sorted in non-decreasing order. Constraints: o 1 <= nums.length <= 104 o -104 <= nums[i] <= 104 o nums is sorted in non-decreasing order. Related Topics: o Array o Two Pointers o Sorting Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?
In this problem we are given an array of numbers and we need to return an array of sorted values.
As a first pass we could take the input array `nums` and traverse it squaring all entries. This would be execution O(n). Then we could sort the updated array in O (n log(n)) which would result in an O(n log(n)) algorithm. After reading the Follow Up section, it seems that we can skip the brute force approach and move into the follow up problem.
We will solve it using the Java programming language and the VSCode IDE on a Windows machine. Since Java is quite portable you could use any other platform and for that matter any other IDE. My suggestion is to use the on-line IDE provided by LeetCode.
public int[] sortedSquares(int[] nums) {
}
The signature of the function of interest is quite simple. We are presented with the input array `num` and should return as output an array with the squared values in ascending order.
-4,-1,0,3,10 main <<< nums: [-4, -1, 0, 3, 10] <<< l: 0 r: 3 output: [0, 0, 0, 0, 100] <<< l: 1 r: 3 output: [0, 0, 0, 16, 100] <<< l: 1 r: 2 output: [0, 0, 9, 16, 100] <<< l: 2 r: 2 output: [0, 1, 9, 16, 100] <<< l: 2 r: 1 output: [0, 1, 9, 16, 100] main <<< output: [0, 1, 9, 16, 100] -7,-3,2,3,11 main <<< nums: [-7, -3, 2, 3, 11] <<< l: 0 r: 3 output: [0, 0, 0, 0, 121] <<< l: 1 r: 3 output: [0, 0, 0, 49, 121] <<< l: 1 r: 2 output: [0, 0, 9, 49, 121] <<< l: 2 r: 2 output: [0, 9, 9, 49, 121] <<< l: 2 r: 1 output: [4, 9, 9, 49, 121] main <<< output: [4, 9, 9, 49, 121] -11,-7,-5,-1,2,4 main <<< nums: [-11, -7, -5, -1, 2, 4] <<< l: 1 r: 5 output: [0, 0, 0, 0, 0, 121] <<< l: 2 r: 5 output: [0, 0, 0, 0, 49, 121] <<< l: 3 r: 5 output: [0, 0, 0, 25, 49, 121] <<< l: 3 r: 4 output: [0, 0, 16, 25, 49, 121] <<< l: 3 r: 3 output: [0, 4, 16, 25, 49, 121] <<< l: 3 r: 2 output: [1, 4, 16, 25, 49, 121] main <<< output: [1, 4, 16, 25, 49, 121] -11,-7,-1,2,5 main <<< nums: [-11, -7, -1, 2, 5] <<< l: 1 r: 4 output: [0, 0, 0, 0, 121] <<< l: 2 r: 4 output: [0, 0, 0, 49, 121] <<< l: 2 r: 3 output: [0, 0, 25, 49, 121] <<< l: 2 r: 2 output: [0, 4, 25, 49, 121] <<< l: 2 r: 1 output: [1, 4, 25, 49, 121] main <<< output: [1, 4, 25, 49, 121] -2 main <<< nums: [-2] <<< l: 0 r: -1 output: [4] main <<< output: [4]
The test cases have a single input line. The line contains a list of integers in ascending order.
Our test scaffold reads the input line and assigns the integer values to the `nums` int[] array. The array is then displayed. As we can see all is well so far.
It appears that the function of interest is called. While executing it displays some values that help us understand and follow the algorithm. Such output is NOT PART OF THE SOLUTION.
When all is said and done, the test scaffold displays the output array.
Please note that the test scaffold is NOT PART OF THE SOLUTION.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read nums int[] ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
// **** call function of interest and display output ****
System.out.println("main <<< output: " + Arrays.toString(sortedSquares(nums)));
}
The test scaffold seems to follow closely the description of the test cases. Will not elaborate any further on it at this time.
/**
* Return an array of the squares of each number
* sorted in non-decreasing order.
*
* 137 / 137 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 41 MB
*
* Runtime: O(n) - Space: O(n)
*/
static public int[] sortedSquares(int[] nums) {
// // **** sanity check(s) ****
// if (nums.length == 1) {
// nums[0] *= nums[0];
// return nums;
// }
// **** initialization ****
int[] output = new int[nums.length];
int l = 0;
int r = nums.length - 1;
// **** traverse output array from right to left - O(n) ****
for (int i = output.length - 1; i >= 0; i--) {
// **** select largest value from the left or right side of nums ****
if (nums[l] * nums[l] > nums[r] * nums[r]) {
output[i] = nums[l] * nums[l];
l++;
} else {
output[i] = nums[r] * nums[r];
r--;
}
// ???? ????
System.out.println("<<< l: " + l + " r: " + r + " output: " + Arrays.toString(output));
}
// **** return output ****
return output;
}
I started the function of interest with a set of statements implementing a sanity check. Not sure it helps much, and since it takes a few lines, I decided to comment it out.
We then initialize a set of variables. The `output` array will hold the squared integers in ascending order. The `l` variable will be used to select the next value from the left side in the `nums` array. Finally, the `r` index will be used to select the next value from the `nums` array coming from the right side.
We then enter a loop that traverses the `output` array from right to left. We will be pulling the squared values from the `nums` array ` from the left or right side.
When done, we return the `output` array which should hold the squared values of the `nums` array in ascending order.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John