Home Blog Page 13

Solving Leetcode 11: Container With Most Water

0

Problem:

From Leetcode

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

From the start we can tell that this is an array question. When it comes to this question it seems that we will be comparing elements with each other. One of the first approach to this problem is to use a double for loop. Unfortunately we know that a double for loop runs in O(N^2) time, which is very inefficient.

2-Pointer Solution

The ideal solution would be to have two pointers, we could call them start and end. The start pointer will start at the beginning of the array (index 0) and the end pointer will start at the end. (height.length -1). Note that we want the index of the array start and end, NOT the element.

Next we know that by starting at each end we can check whether or not the previous or next element is higher or or not. If so we set the new pointer to higher element and update the area.

  1. Keep two index, start= 0 and end = n-1 and a value area that stores the maximum area.
  2. Run a while loop until first is less than the last.
  3. Update the area with maximum of area and min(array[first] , array[last])*(last-first)
  4. if the value at array[first] is greater the array[last] then update last as last – 1 else update first as first + 1
  5. Print the maximum area.

Code Here:

class Solution {
    public int maxArea(int[] height) {

        int area = 0;

        int start = 0;

        int end = height.length - 1;

        while(start < end){
            int top = Math.min(height[start], height[end]);

            int newArea = top*(end-start);
            area = Math.max(area, newArea);

            if(height[start]< height[end]){
                start++;
            }
            else{
                end--;
            }
        }
     return area;   
    }
}

We can find the maximum area under a histogram using two pointers. The pointers start at the beginning and end of the histogram, and we move them inward until they meet. At each step, we calculate the area of the rectangle formed by the two pointers and the current height of the histogram. The maximum area is the largest area we calculate.

This algorithm is simple to implement and has a time complexity of O(n). It is a good choice for finding the maximum area under a histogram when the histogram is large.

How to Reverse a String in JavaScript

0

Reversing a string isn’t uncommon in development, and fairly popular for entry-level interview questions. With JavaScript, we have many ways to reverse a string. We can use a combination of string’s split() method as well as array’s reverse() and join() methods (since strings are ultimately arrays of characters).

Method 1: Using Built-in Methods to Reverse the String – split(), reverse() and join()

We can use the string’s split() method to create an array of characters from the original string. We can then call the array’s reverse() method to reverse the order of elements in the array. Finally, we can use the join() method to convert the reversed array back into a string:

let str = 'Hello World';
string = [...str ].reverse().join("");

console.log(str ); // "dlroW olleH"

Here, the Spread Syntax is used to split the string into an array and is functionally equivalent to the split() method, which you could also use instead. To understand why they all work together, let’s overview what each function does. split() The split() method returns a new array of strings after splitting a string with the provided separator:

string.split(separator, limit) The separator defines where the string splits into an element in the resulting array. We can define the number of the array element with the limit parameter. When we use the split() method with an empty string, ”, the string will be split on every character. It will come in handy when we convert our string into an array of individual characters.

We’ll also look at a little more complex example of nested if statements, where the condition only applies to specific elements. The syntax for this is shown in Listing 4-20.

[...myVar, 4, 5, 6] // combines myVar array with the given elements
myFunc(...myVar) // Use the myVar's elements as argument to the function

When the spread operator is used with a string, the string is converted into a sequence of characters:

let str = 'hello';
console.log([...str]); // ["h","e","l","l","o"]
console.log(str.split('')); // ["h","e","l","l","o"]
str.reverse()

The reverse() returns a reversed array, in-place. That’s to say – the original array is reversed instead of a copy that’s returned as the result:

//JavaScript
let str = ['a','b','c','d'];
let reversedStr = str.reverse();
console.log(str); // ["d","c","b","a"]
console.log(reversedStr); // ["d","c","b","a"]

You don’t need to declare a new variable, but we frequently do in order to rename the variable name to something more descriptive.

Using a for Loop to Reverse the String

/* With a for loop, we can iterate over each character from the string. Starting from the end of the string to the beginning of the string - we can continuously append the characters to a new string and thus form a reversed string:
*/

const str = 'guitar';
console.log('The original string is: ' + str);
let reversedStr = '';

for (let i = str.length - 1; i >= 0; i--) {
  reversedStr += str[i];
}

console.log('The reversed string is: ' + reversedStr);

Here, we created an empty string, reversedStr, to hold the reversed string. String indices are like array indices, they start at 0. Therefore, we started the loop from one less than the length of the string (picking up the letter r) and loop till our counter goes to 0 (with the letter g).

The reversedStr variable concatenates the elements of the string.

Running the code gives us this output:

The original string is: guitar

The reversed string is: ratiug

function getNumber{
console.log("this is a number");
}

Testing for code block

function getNumber{
console.log("this is a number");
}