DEV Community: Stylus07

Container With Most Water

Stylus07 — Tue, 03 May 2022 21:41:26 +0000

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.

Problem statement taken from: https://leetcode.com/problems/container-with-most-water/

Brute Force Approach

var maxArea = function (heights) {
    let maxArea = 0;
    for (let p1 = 0; p1 < heights.length; p1++) {
        for (let p2 = p1 + 1; p2 < heights.length; p2++) {
            const length = Math.min(heights[p1], heights[p2]);
            const width = p2 - p1;
            const area = length * width;
            maxArea = Math.max(area, maxArea);
        }
    }
    return maxArea;
}

Time Complexity : O(n^2)
Space Complexity : O(1)

Optimized Approach

    let maxArea = 0, p1 = 0, p2 = heights.length - 1;
    while (p1 < p2) {
        const height = Math.min(heights[p1], heights[p2]);
        const width = p2 - p1;
        const area = height * width;
        maxArea = Math.max(maxArea, area);
        if (heights[p1] <= heights[p2]) {
            p1++;
        } else {
            p2--;
        }
    }
    return maxArea;

Time Complexity : O(n)
Space Complexity : O(1)

Logger Rate Limiter

Stylus07 — Sun, 01 May 2022 20:01:52 +0000

Design a logger system that receives a stream of messages along with their timestamps. Each unique message should only be printed at most every 10 seconds (i.e. a message printed at timestamp t will prevent other identical messages from being printed until timestamp t + 10).

All messages will come in chronological order. Several messages may arrive at the same timestamp.

Implement the Logger class:

1. Logger() Initializes the logger object.
2. bool shouldPrintMessage(int timestamp, string message) Returns true if the message should be printed in the given timestamp, otherwise returns false.

var Logger = function() {
    this.map = new Map();
};

Logger.prototype.shouldPrintMessage = function(timestamp, message) {
   if(this.map.has(message)){
       const prevTime = this.map.get(message);
       if(timestamp < prevTime + 10) return false;
   }
   this.map.set(message, timestamp);
   return true;
};

Longest Consecutive Sequence

Stylus07 — Wed, 20 Apr 2022 04:45:40 +0000

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

var longestConsecutive = function (nums) {
    let num_set = new Set(nums);
    let longestStreak = 0;
    for (let num of nums) {
        if (!num_set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;
            while (num_set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }
            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }
    return longestStreak;
}

Time Complexity : O(n)

Encode and Decode Strings

Stylus07 — Wed, 20 Apr 2022 02:54:56 +0000

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

var encode = function (strs) {
    let res = '';
    for (let char of strs) {
        res += (char.length).toString() + `#` + char;
    }
    return res;
}

var decode = function (s) {
    let res = [];
    for (let i = 0; i < s.length; i++) {
        let j = i;
        while (s[j] != '#') {
            j++;
        }
        let wordLength = parseInt(s.substring(i, j));
        res.push(s.substring(j + 1, j + 1 + wordLength));
        i = j + wordLength;
    }
    return res;
}

Time Complexity : O(n)

Group Anagrams

Stylus07 — Sun, 17 Apr 2022 19:42:15 +0000

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

var groupAnagrams = function (strs) {
    if (!strs || !strs.length) {
        return null;
    }
    let anagrams = {};
    for (let x = 0; x < strs.length; x++) {
        const sortedWord = strs[x].split('').sort().join();
        if (sortedWord in anagrams) {
            anagrams[sortedWord].push(strs[x])
        } else {
            anagrams[sortedWord] = [strs[x]];
        }
    }
    return Object.values(anagrams);
}

Time Complexity : O(w*n*log(n))
Space Complexity : O(wn)

Valid Anagram

Stylus07 — Mon, 11 Apr 2022 03:10:33 +0000

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

var isAnagram = function (s, t) {
    if (s.length !== t.length) {
        return false;
    }
    let countS = new Map();
    let countT = new Map();
    for (let start = 0; start < s.length; start++) {
        countS.set(s[start], 1 + (countS.get(s[start]) ? countS.get(s[start]) : 0));
        countT.set(t[start], 1 + (countT.get(t[start]) ? countT.get(t[start]) : 0));
    }

    for (const [key, value] of countS) {
        if (countS.get(key) !== countT.get(key)) {
            return false;
        }
    }
    return true;
}

Time Complexity : O(n)
Space Complexity : O(s+t)

Contains Duplicate

Stylus07 — Sun, 10 Apr 2022 17:06:53 +0000

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct

Brute Force Approach
Time Complexity : O(n^2)
Space Complexity : O(1)

Sort Approach
Time Complexity : O(nlogn)
Space Complexity : O(1)

Optimized Approach via hash

var containsDuplicate = function (nums) {
    let hashMap = {};
    for (let num of nums) {
        if (num in hashMap) {
            return true;
        }
        hashMap[num] = 1;
    }
    return false;
}

Time Complexity : O(n)
Space Complexity : O(n)

Peak Index in a Mountain Array

Stylus07 — Fri, 03 Dec 2021 02:30:30 +0000

Problem

Let's call an array arr a mountain if the following properties hold:
arr.length >= 3

There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
Given an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

Brute Force Approach

var peakIndexInMountainArray = function(arr) {
    let count =0;

    for(let start=0; start < arr.length; start++){
        if(arr[start] < arr[start+1]){
            count+=1;
        }
    }
    return count;
};

Intersection of Three Sorted Arrays

Stylus07 — Fri, 03 Dec 2021 00:43:13 +0000

Problem:

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

var arraysIntersection = function(arr1, arr2, arr3) {
    let p1=0;
    let p2=0;
    let p3=0;

    let ans = [];

    while(p1 < arr1.length && p2< arr2.length  && p3 < arr3.length){

        if(arr1[p1] === arr2[p2] && arr2[p2] === arr3[p3]){
            ans.push(arr1[p1]);
            p1++;
            p2++;
            p3++;
        }else{
            if(arr1[p1] < arr2[p2]){
                p1++;
            }else if(arr2[p2] < arr3[p3]){
                p2++;
            }else{
                p3++;
            }
        }
    }
    return ans;
};

Change the document title on react application

Stylus07 — Sun, 21 Oct 2018 17:13:08 +0000

As a beginner in react, i developed the application by running the one command create-react-app.

By default, the app will be generated with the below title

<title>React App</title>

And it's pretty simple to change, just by having this life-cycle hook into your app file

  componentDidMount() {
    document.title = 'Custom Title';
  }
~~~~

Now your application title will be changed to your custom title