DEV Community: Kira

Leetcode 26: Remove Duplicates from Sorted Array

Kira — Sun, 23 Aug 2020 13:50:52 +0000

This problem is part of the Introduction to Data Structures Arrays-101 section in LeetCode.

Problem Statement

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

Solution

Two pointers

The given array is a sorted array, so duplicate numbers will be group together. First, we can handle the edge case of empty array. Then we can start iterating elements from the head.

The second pointer will go through all elements in the list, and the first pointer only move when meeting the unique number.

var removeDuplicates = function(nums) {
   // Handling Edge Case
   if(nums.length === 0 ) return 0
     let p1 = 0
     for(let p2 = 1; p2< nums.length; p2++){
        if(nums[p1] !== nums[p2]){
            p1++;
            nums[p1] = nums[p2]
        }       
     }
    return p1 +1        
}

Beside, we can also start iterator from the end of array. If the value of two pointer is the same, then remove the element.

var removeDuplicates = function(nums) {
    // Handling Edge Case
    if(nums.length === 0 ) return 0
    for(let i = nums.length-1; i > 0;i--){
        if(nums[i]===nums[i-1]){
            nums.splice(i,1)
        }
    }
    return nums.length
};

Leetcode 1299: Replace Elements with Greatest Element on Right Side

Kira — Sun, 23 Aug 2020 11:45:49 +0000

This problem is part of the Introduction to Data Structures Arrays-101 section in LeetCode.

Problem Statement

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with 1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Constraints:

1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5

Solution 1: two loops

var replaceElements = function(arr) {
    let newArr = []
    for(let i=0; i<arr.length; i++){    
        let max = arr[i+1]
        for(let j=i+1;j<arr.length;j++){
            let value = arr[j+1]
        max = value > max? value: max
        }
        newArr.push(max)
    }
    newArr[arr.length-1] = -1
    return newArr
};

Time complexity : O(n²)
Space complexity : O(n)

Solution 2: One loop

With last index as -1, we can start from the rightmost element, move to the left side one by one, and keep track of the maximum element. Replace every element with the maximum element.

For example:

let arr = [17,18,5,4,6,1]

and as we know:

newArr[5] is -1
newArr[4] is equal to arr[5]
newArr[3] is equal to the maximum number among arr[4] to arr[5]. This is also equal to the maximum number among arr[4] to newArr[4]

To simplify the logic, we can describe like this:

newArr[0] = max(arr[1:5]) = max(arr[1], newArr[1])
newArr[1] = max(arr[2:5]) = max(arr[2], newArr[2])
newArr[2] = max(arr[3:5]) = max(arr[3], newArr[3])
newArr[3] = max(arr[4:5]) = max(arr[4], newArr[4])
newArr[4] = arr[5]
newArr[5] = -1

And the solution will be:

var replaceElements = function(arr) {
    let newArr = [];
    newArr[arr.length-1] = -1;
    for (i = arr.length-2; i >= 0; i--) {
        newArr[i] = Math.max(newArr[i+1],arr[i+1]);
    }
    return newArr;
};

Time complexity : O(n)
Space complexity : O(n)

Leetcode 1346: Check If N and Its Double Exist

Kira — Tue, 11 Aug 2020 14:46:19 +0000

This problem is part of the Introduction to Data Structures Arrays-101 section in LeetCode.

Problem Statement

Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exists two indices i and j such that :

i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]

Example 1

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

Constraints:

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

First thought - Solution 1: two loops

 var checkIfExist = function(arr) {
     for(let i=0;i<arr.length;i++){
         let target = arr[i]
         for(let j=i+1;j<arr.length;j++){
             if(target === arr[j]*2 || target === arr[j]/2){
                 return true
             }
         }
     }
     return false
 };

Time complexity : O(n²)
Space complexity : O(n)

Solution 2: hash table

We could also use hash table data structure to solve this problem using Set object or array.

Iterate over the array and check if element in array multiplied by 2 or divided by 2 is equal to the element in the Set object.
If existed, then return true
If not existed, then add the element in the Set object.

var checkIfExist = function (arr){
    let newSet = new Set()
    for(let i=0;i<arr.length;i++){
        if(newSet.has(arr[i]/2) || newSet.has(arr[i]*2)){
            return true
        }else{
            newSet.add(arr[i])
        }
    }
      return false
}

NOTE: considering 0 in array

[0,0] - output is True
[0,10,7,1] - output is False

Time complexity : O(n)
For each element, we try to find its match in the Set object by looping through the array which takes O(n) time.

Space complexity : O(n)
The space complexity is O(n) because it needs a variable newSet to store the data.

How to use jest-emotion and Enzyme to test Emotion Component Styling

Kira — Tue, 11 Aug 2020 06:24:10 +0000

Emotion is a powerful CSS-in-JS library. In this article, we will see how to start testing components' style when using emotion with React.

Note:
Using Emotion 10, React > 16.3., Enzyme v3.x

Adding Enzyme to Project

yarn add enzyme enzyme-adapter-react-16

Alternatively, you may use npm:

npm install enzyme enzyme-adapter-react-16

As of Enzyme 3, you will need to install Enzyme along with an Adapter corresponding to the version of React we are using. (Here we use the adapter for React 16)

The adapter will also need to be configured before testing case.

src/example.test.js

import { configure } from 'enzyme';
import Adapter from 'enzyme-adapter-react-16';

configure({ adapter: new Adapter() });

Adding jest-emotion

Jest-emotion is a Jest testing utilities for emotion. It allows us to add specific matchers to our test case.

yarn add install jest-emotion

Testing Functional Component

src/example.js

import React from 'react'
import {css} from 'emotion'

function Example(props){
    const {type} = props
    let color;
     switch (type) {
        case 'csv':
            color = '#ffc307';
            break;
        case 'json':
            color = '#00adef';
            break;
    }

    return <div style={{backgroundColor:`${color}`}}>{type}</div> 
}

export default Example

In this case, we want to check the background-color style based on props.

Writing test cases

Here we need toHaveStyleRule matcher from jest-emotion to find the style rule of components.

src/example.test.js

import React from 'react'
import { configure, shallow } from 'enzyme'
import { matchers } from 'jest-emotion'
import Adapter from 'enzyme-adapter-react-16'
import Example from './Example'

configure({adapter: new Adapter()})
expect.extend(matchers)

describe('test Example component',()=>{
    it('background color is #ffc307 and text is csv when props type is csv',()=>{
        const formatType = 'csv'
        const wrapper = shallow(<Example type={formatType}/>)
        expect(wrapper.text()).toEqual('csv')
        expect(wrapper).toHaveStyleRule('background-color','#ffc307')
    })

     it('background color is #00adef and text is json when format type is json',()=>{
        const formatType = 'json'
        const wrapper = shallow(<Example type={formatType}/>)
        expect(wrapper.text()).toEqual('json')
        expect(wrapper).toHaveStyleRule('background-color','#00adef')
    })
})