DEV Community: Bharath Sriraam R R

How do you make responsive designs in React?

Bharath Sriraam R R — Sun, 09 Aug 2020 09:06:17 +0000

How do you peeps handle responsive design in React when using UI libraries like Material-UI and antd? For example converting a side drawer in desktop to a bottom bar in mobile. I'm looking for something that doesn't re-render a lot and is fast.

LeetCode Challenge: Counting Elements

Bharath Sriraam R R — Wed, 15 Apr 2020 10:03:33 +0000

This is the last problem in Week 1 of the month-long LeetCode challenge.

Looks like this is the first of the 5 new questions that were promised to make things interesting.

Problem

Given an integer array arr, count element x such that x + 1 is also in arr.

If there're duplicates in arr, count them separately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:

1 <= arr.length <= 1000
0 <= arr[i] <= 1000

Clarification

The first 3 test cases are kind of misleading because they don't really show what is actually expected from us.

However, the last example gives some info.

From what we can observe, they're asking for the count of x in the array if x+1 also exists in the array.

Approach 1: Space Optimized

If the array is sorted then x+1 will be right after x. But if there are multiple occurrences of x then the 1st x+1 will come after the last x.

So, we need to count the frequency of each x and if the next element is different we need to check if it is x+1 or not.

Algorithm:

Initialize variables count to store the final result and currCount to store the count of the current element that is being tracked.
Sort the array
Iterate through the array
If the current element is equal to the previous element then increment currCount
Else if the current element is 1 greater than the previous element then add currCount to count. Reset currCount.
Return count

Code:

def approach1(arr):
    if len(arr) == 1:
        return 0

    arr = sorted(arr)
    count = 0
    currCount = 1

    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            currCount += 1
        else:
            if arr[i] == arr[i-1] + 1:
                count += currCount
            currCount = 1

    return count

Complexity analysis:

Time complexity: O(n*log(n)) 
Space complexity: O(1)

Approach 2: Time Optimized

Since we're dealing with counts we can use a hash map to maintain the count of each number and then easily check for the presence of the next number.

Code:

def approach2(arr):
    count = 0
    freq = {}

    for num in arr:
        freq[num] = freq.get(num, 0) + 1

    for x in freq:
        if x+1 in freq:
            count += freq[x]

    return count

Complexity analysis:

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

Summary

Not many people talk about this but sometimes a programmer needs to consider the tradeoffs between space and time complexity of different solutions because not all situations have enough space to achieve optimal runtime complexity. The same applies the other way around.

As usual,

LeetCode Challenge: Group Anagrams

Bharath Sriraam R R — Wed, 15 Apr 2020 09:37:38 +0000

I've always wondered if Anagrams and Palindromes will ever be useful in real life. Sometimes, I think of a use case but just checking if 2 things are anagrams or palindromes doesn't really prove to be useful.

However, problems like this mess with your brain in a way that makes them fearsome and I like stuff like that which is why I respect them despite their uselessness.

Problem

Given an array of strings, group anagrams together.

Example:

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

Note:
All inputs will be in lowercase.
The order of your output does not matter.

Approach 1: The Lazy method

If you're lazy like me then you'll know that the laziest way to code if 2 strings are anagrams is to sort them and check for equality.

Algorithm:

Initialize a Hash Map called groups
Iterate through the array
For each string find the sorted string which is the key and append the string to the list of anagrams.
Return the list of all values in the hash map.

Code:

def approach1(arr):
    groups = {}

    for s in arr:
        key = ''.join(sorted(list(s)))
        groups[key] = groups.get(key, []) + [s]

    return list(groups.values())

Complexity Analysis:

Time Complexity: O(n*k*log(k)), where n is the length of arr, and k is the maximum length of a string in strs. 

Space Complexity: O(n*k), the size of the hash map

Approach 2: Paying Attention

The above approach would have worked for any kind of data where each element is quantifiable.

But in this situation our data space is limited.

We are only dealing with lowercase english alphabets. In other words, there are only 26 possible characters in each string.

So, we can use the frequency of each alphabet to uniquely group anagrams.

But, what will the key be for our new hashmap?

The array of 26 frequencies will be unique but we can't keep an array as a key in a normal hashmap(language exceptions excluded).

Until now we've used either numbers or strings as the key.
If we can transform our array into a number or a string then our problem will be solved.

What could this transformer function be?

How about constructing a string with some non-numerical character between consecutive numbers?

Now, that we know the algorithm let's code!

Code:

def approach2(arr):
    groups = {}
    for s in arr:
        freq = [0 for i in range(26)]

        for c in s:
            freq[ord(c) - ord('a')] += 1

        freq = list(map(str, freq))
        key = ':'.join(freq)

        groups[key] = groups.get(key, []) + [s]

    return list(groups.values())

Complexity Analysis:

Time Complexity: O(n*k), where n is the length of arr, and k is the maximum length of a string in strs. 

Space Complexity: O(n*k), the size of the hash map

Summary

Paying attention is very important to make those "wow" optimizations.

The replit for this problem:

LeetCode Challenge: Best Time to Buy and Sell Stock II

Bharath Sriraam R R — Mon, 13 Apr 2020 21:33:43 +0000

This is one of those problems which when you solve, you take a small step towards going to the next level.

Problem

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note:
You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Initial thoughts

Since it's a real situation there's no need to find a realistically close situation and simulate it.

If you try observing what you would do in real life it's simple to notice the steps and write an efficient algorithm.

However if unfortunately, you're unable to do so then you would probably try all possible combinations of trades and find the combo with the maximum profit. This is what approach 1 is about.

Approach 1

The goal is to recursively calculate max profit possible for trades starting from all possible indices.

Algorithm:

Define the recursive function nextMaxProfit with parameters: prices which is the array and today which is the starting index from which the function will calculate the max profit.
The stopping condition or base case for the recursion is if the today param is out of bounds.
Initialize totalMax to store the max profit for trades starting from today.
Iterate variable start from today till the end of prices
Initialize maxprofit to zero in each iteration of step 4
Iterate from start+1 till the end of the array and if current price is greater than prices[start] then recalculate maxprofit
After the end of step 6 recalculate totalMax
Return totalMax

Code:

def approach1(prices):
    return nextMaxProfit(prices, 0)


def nextMaxProfit(prices, today):

    if (today >= len(prices)):
        return 0

    totalMax = 0
    for start in range(today, len(prices)):
        maxprofit = 0
        for i in range(start+1, len(prices)):
            if (prices[i] > prices[start]):
                profit = nextMaxProfit(prices, i + 1) + prices[i] - prices[start]
                if (profit > maxprofit):
                    maxprofit = profit

        if (maxprofit > totalMax):
            totalMax = maxprofit

    return totalMax

Complexity analysis:

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

Approach 2

Ask yourself

What would I do in real life, if I was given this situation?

You'd think something like:

I'll buy the first day's stock
If the next day's price is not decreasing then wait
The moment it goes down then I sell and buy the current stock and repeat

And it makes sense because you're assuming you have an infinite budget which works for this question.

Since that covered the algorithm let's look at the code.

Code:

def approach2(prices):
    if len(prices) == 0:
            return 0

    ans = 0
    buy = prices[0]
    sell = prices[0]

    for i in range(1, len(prices)):
        if prices[i] < sell:
            ans += sell - buy
            buy = prices[i]

        sell = prices[i]

    ans += sell - buy
    return ans

Complexity analysis:

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

Summary

There are many variants of this that you can try on LeetCode if you're interested.

Here's the replit

LeetCode Challenge: Move Zeroes

Bharath Sriraam R R — Sat, 11 Apr 2020 17:32:11 +0000

If you've been following this series so far, then this problem should be a piece of cake.

Problem

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Approach 1

Algorithm:

Initialize variable zeroCount to store count of zeroes
Initialize result to store the final array
Iterate through all elements of the array
If the element is zero then increment zeroCount
Else append to the result array
Append zeroCount number of zeroes to the result
Replace elements of original array with result

Code:

def approach1(nums):
    zeroCount = 0
    result = []

    for i in range(len(nums)):
        if nums[i] == 0:
            zeroCount += 1
        else:
            result.append(nums[i])

    for i in range(zeroCount):
        result.append(0)

    for i in range(len(nums)):
        nums[i] = result[i]

    return nums

Complexity analysis:

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

Approach 2

Algorithm:

Initialize variable nextIndex to store the next index of non zero element
Iterate through all elements of the array
If the current element is not zero then put it at nextIndex and increment it
Once step 2 ends iterate from nextIndex to the end of the array and assign zero at those indices

Code:

def approach2(nums):
    nextIndex = 0

    for i in range(len(nums)):
        if nums[i] != 0:
            nums[nextIndex] = nums[i]
            nextIndex += 1

    for i in range(nextIndex, len(nums)):
        nums[i] = 0

    return nums

Complexity analysis:

Time complexity: O(n) with near minimum operations
Space complexity: O(1)

Approach 3

Algorithm:

Initialize variable nextIndex to store the next index of non zero element
Iterate through all elements of the array
If the current element is not zero then swap it with the element at nextIndex and increment it

Code:

def approach3(nums):
    nextIndex = 0

    for i in range(len(nums)):
        if nums[i] != 0:
            nums[i], nums[nextIndex] = nums[nextIndex], nums[i]
            nextIndex += 1

    return nums

Complexity analysis:

Time complexity: O(n) with minimum operations
Space complexity: O(1)

Summary

This problem was more of tricky thinking rather than algorithmic thinking.

Here's the replit

LeetCode Challenge: Maximum Subarray

Bharath Sriraam R R — Fri, 10 Apr 2020 14:57:41 +0000

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

What is a contiguous subarray?

Approach 1: A very intuitive and insanely slow solution

Now, that you know what a contiguous subarray is, the only thing left to do is to figure out which subarray has the maximum sum.

Since we don't know the length or position of the subarray we seek, we can perform an exhaustive search of all possible subarray lengths starting from all possible indices.

Algorithm:

Initialize the answer to the first element of the array
Iterate sub_len from 1 to length of the array
Iterate start_idx from 0 to length of the array
Assign answer to the maximum among the previous answer and sum of elements in the array from index start_idx to start_idx + sub_len

Code:

def approach1(nums):
    ans = nums[0]
    for sub_len in range(1, len(nums) + 1):
        for start_idx in range(len(nums)):
            ans = max(ans, sum(nums[start_idx : start_idx + sub_len]))
    return ans

Pretty sweet code right? Have a look at the Time complexity.

Complexity analysis:

Time complexity: O(n^3) 😱
Space complexity: O(1)

Approach 2: Slightly improved version of Approach 1

If you analyze the weakness of the previous algorithm, for each valid start_idx we calculate the sum by iterating from start_idx to start_idx + sub_len which is duplicate work.

Why is it duplicate work?
In each subarray, we leave 1 element from the start and add 1 element to the end. Which means the sum of the remaining elements from the previous subarray need not be calculated. Here's an illustration to simplify it:

Which means, we can subtract the first element of the previous subarray and add the last element of the new subarray to the sum of the previous subarray.

Algorithm:

Initialize the answer to the first element of the array
Iterate sub_len from 1 to length of the array
Iterate start_idx from 0 to length of the array
Assign answer to the maximum among the previous answer and sum of elements in the array from index start_idx to start_idx + sub_len

Code:

def approach2(nums):
    ans = nums[0]
    length = len(nums)

    for sub_len in range(1, length + 1):
        subsum = sum(nums[0 : sub_len])
        ans = max(ans, subsum)

        for start_idx in range(1, length):
            if (start_idx + sub_len - 1) < length:
                subsum = subsum - nums[start_idx - 1] + nums[start_idx + sub_len - 1]
                ans = max(ans, subsum)
            else:
                break

    return ans

This is better but you'll still get a TLE(at least in Python you will).

Complexity analysis:

Time complexity: O(n^2) 😕
Space complexity: O(1)

Approach 3:

Clearly, this kind of thinking is not getting us anywhere so time to take a step back and think differently.

Let's say we have a subarray with sum X and the next element is Y.
If X+Y < Y then we would be better off starting a new subarray from Y because it makes no sense to have a subarray with a sum less than its greatest element.

Here's an example:

Array: [-2,1,-3,4,-1,2,1,-5,4]

sum = -2 because it's the initial element

sum + 1 = -1 and -1 < 1 so we wouldn't consider the subarray [-2, 1]

So, sum = 1

sum + (-3) = -2 and -2 > -3 so we consider the subarray [1, -3]

sum + 4 = 2 and 2 < 4 so we don't consider [1, -3, 4] instead we start a new subarray from 4.

So, sum = 4 and subarray = [4]

and so on...

This looks good but how do we get the maximum subarray sum?
Simple, we use another variable to keep track of the maximum subarray sum whenever we change the subarray.

Algorithm:

Initialize ans and subarr_sum to the first element of the array
Iterate from index 1 to last index of the array
Assign subarr_sum = max(nums[i], nums[i] + subarr_sum)
Assign ans = max(ans, subarr_sum)
return ans

Code:

def approach3(nums):
    ans = nums[0]
    subarr_sum = nums[0]

    for i in range(1, len(nums)):
        subarr_sum = max(nums[i], nums[i] + subarr_sum)
        ans = max(ans, subarr_sum)

    return ans

Complexity analysis:

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

Now, you be like

Summary

Wasn't the solution behind Approach 3 pretty intuitive?
Guess what! The algorithm used in it is an example of Dynamic Programming!

What is Dynamic Programming?

Here's what Wikipedia says:

Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

You can read about it in detail over here but basically, you identify sub-problems and somehow find solutions to them and save it so that you don't calculate it again.

Where was this used here?
The variable subarr_sum was used to store the maximum subarray sum so far, which means at any index we knew the answer to the problem so far which is the subproblem. All we had to do was make a decision whether to include this element in the subarray or to start a new subarray.

Here's the replit

There's a saying related to dynamic programming:

LeetCode Challenge: Happy Number

Bharath Sriraam R R — Thu, 09 Apr 2020 17:12:36 +0000

This is the second question in the LeetCode 30 Day Challenge.

Problem

Write an algorithm to determine if a number n is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example:

Input: 19
Output: true
Explanation: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Before I explain various ways to solve this problem, I want to say that this problem is kind of stupid and interesting at the same time. You'll probably understand why once you solve it.

Initial Thoughts

After reading the problem statement you may have jumped into an editor and started writing code. Probably something like this

def sum_of_squares(n):
    s=0
    while n > 0:
        x = n%10
        s += x*x
        n //= 10
    return s

def solution(n):
    while True:
        n = sum_of_squares(n)

        if n == 1:
            return True
        else:
            # what do i do?

Now that you realize you might have missed something in the problem statement, you read it again and come across a very important hint:

or it loops endlessly in a cycle which does not include 1

It says that an unhappy number will loop endlessly in a cycle. This means that the sum of squares will eventually repeat.

So, all we need to do is check if we came across a repeated number other than 1. If so, we know that the original number is unhappy.

Approach 1:

In the last post, we came across 2 interesting data structures: Hash Maps and Hash Sets. Both of them help in storing unique data. Let's use a Hash Set since we don't need to store a key-value pair.

Algorithm:

Write a function to return the sum of squares of the digits of a number
Initialize an empty hashset called visited
Iterate infinitely
If num == 1 return True
Replace num with the sum of squares of its digits
If new num exists in visited return False otherwise add it to the set

Code:

def sum_of_squares(n):
    s=0
    while n > 0:
        x = n%10
        s += x*x
        n //= 10
    return s


def approach1(n):
    visited = set()
    while True:
        if n == 1:
            return True

        n = sum_of_squares(n)

        if n in visited:
            return False

        visited.add(n)

Complexity analysis:

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

Note

The previous algorithm has the best time complexity you can achieve so the following solutions will only improve space complexity. There are many other solutions that exploit various properties of Happy numbers but I want to use this as an opportunity to show an important concept and pattern used in Linked List problems.

Approach 2

As mentioned in the Note, this solution will be based on a common pattern used in Linked List problems. If you're not familiar then learn about them here.

The question is to find whether a linked list has a cycle in it or not.

This is how a linked list with a cycle looks like:

You can solve this problem using Hash Sets but the objective is to solve it with constant space complexity.

How? Two Pointers!

If two people run at different speeds in a circle, they eventually meet.

Now, you might wonder why will this always work? Here's the best proof I have come across. It uses simple modular arithmetic to explain it very intuitively.

If you're still not convinced then here's a natural example everybody comes across everyday but goes unnoticed.

The hands of a clock

The minute and hour hand of a clock move at different speeds, but they coincide 22 times a day. The above image shows 11 such times. These occur twice in a day every 12 hours resulting in 22 times. The times they coincide are weird which is why we don't notice them but they do.

They coincide because the space they move through is limited in the circle and since one hand is faster they are bound to meet.

The 2 pointers in a linked list are the same. They can move at any 2 speeds and they will meet if there is a cycle.

Can I use any 2 speeds for the pointers?

Yes, you can. However, we don't know how many minimum elements will be present in the cycle which is why 1:2 is the most common speed chosen.

So, you keep 2 pointers called slowptr and fastptr.
Initially, slowptr points to the head of the linked list and fastptr points to the 2nd element. Until slowptr and fastptr point to the same node you increment slowptr by 1 node and fastptr by 2 nodes.
If fastptr has crossed the end or is at the end while slowptr and fastptr are not the same then it means that there is no cycle.

All right, but how to use this?

In the Linked list problem slowptr and fastptr were variables that held nodes of the linked list, but since we're dealing with numbers we need to store numbers.

We increment nodes in a linked list so in our problem we get the next number with the sum_of_squares function. Now that we know how to use 2 pointers in our problem let's write the algorithm.

Algorithm:

Write a function to return the sum of squares of the digits of a number
Initialize slow = sum_of_squares(n)
Initialize fast = sum_of_squares(slow)
Iterate while slow != fast
Assign slow = sum_of_squares(slow)
Assign fast = sum_of_squares(fast) twice
If fast == 1 return True
When Step 4 ends, return slow == 1 because if n was 1 then step 4 wouldn't have begun.

Code:

def sum_of_squares(n):
    s=0
    while n > 0:
        x = n%10
        s += x*x
        n //= 10
    return s


def approach2(n):
    slow = fast = n

    slow = sum_of_squares(slow)
    fast = sum_of_squares(slow)

    while slow != fast:
        slow = sum_of_squares(slow)
        fast = sum_of_squares(fast)
        fast = sum_of_squares(fast)

        if fast == 1:
            return True

    return slow == 1

Complexity analysis:

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

Summary

Earlier in this post, I said that this problem was both stupid and interesting. It's stupid because at first glance it seems very easy and doesn't have any programmatic relevance. It's interesting because it can be used to learn something totally different but very useful.

I hope you understood the 2 pointer method because it can be used to solve many unrelated and weird problems efficiently in terms of both time and space.

Here's the repl for this problem.

Have fun coding ✨

LeetCode Challenge: Single Number

Bharath Sriraam R R — Wed, 08 Apr 2020 12:52:19 +0000

Problem description

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Let's solve

As I mentioned in the introductory post, if you're a beginner don't solve while trying to achieve the optimal runtime complexity in your first try. So, ignore the Note.

Approach 1

If you're not familiar with a fancy data structure like Hash Map(aka Dictionary) you would have thought that if an element doesn't exist to the left and to the right in the array then it is the single number and you're right!.

Algorithm:

Iterate over all elements of the array
Let the current element be ele and index be idx
If ele doesn't exist in array[:idx] and array[idx+1:] then return ele

Code:

def approach1(nums):
    for idx in range(len(nums)):
        ele = nums[idx]

        if ele not in nums[:idx] and ele not in nums[idx+1:]:
            return ele

Complexity analysis:

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

Approach 2

Upon careful analysis of the previous code, the main bottleneck is that we don't know where the 2nd occurrence of an element resides. Hence, we are forced to search for every element to the left and right of the current element.

What if we did something to the array so that we knew where the 2nd occurrence is for each element?

Sorting to the rescue!

Sorting a list of numbers means arranging them in an increasing or decreasing order.

How does this help?

Since each element occurs twice except a single element, in the sorted array similar elements will be next to each other.

Example 1:

Input: [4, 1, 2, 1, 2]
Sorted Output: [1, 1, 2, 2, 4]

Example 2:

Input: [6, 2, 4, 1, 3, 4, 1, 2, 6]
Sorted Output: [1, 1, 2, 2, 3, 4, 4, 6, 6]

Now, we see that we can easily find the element that occurs once because if it is in the middle then it will be at an even indexed position otherwise it'll be at either end of the array.

Algorithm:

Sort the array and let len = length of array
If len == 1 then return array[0]
If array[0] != array[1] then return array[0]
If array[len - 1] != array[len - 2] then return array[len - 1]
Iterate over even indexed elements and if array[i] != array[i + 1] then return array[i]

Code:

def approach2(nums):
    nums = sorted(nums)
    length = len(nums)

    if length == 1:
        return nums[0]

    if nums[0] != nums[1]:
        return nums[0]

    if nums[length - 1] != nums[ length - 2]:
        return nums[length - 1]

    for i in range(0, length, 2):
        if nums[i] != nums[i + 1]:
            return nums[i]

Complexity analysis:

Time complexity: O(n*log(n)) 
Space complexity: O(1)

Approach 3

If we sort the array, then it will be slow for really huge arrays.

Let's take a step back and observe how a person with no programming knowledge whatsoever would solve this. Let's call this person Saitama.

Saitama would take a paper and write down each element and if its count is greater than 1, then he would either strike it or increment the count.

Then he would go through this list looking for the element that wasn't struck or whose count is equal to 1.

But how do we get this magical notebook where we can note down elements and their counts in code?

Introducing the Map ADT

A Map is an abstract data type(ADT) with the following properties:

Consists of key-value pairs called items

Each item must be unique and is identified by the key.

You can add/modify/remove items only with the key

Keys may also be modified

It should be iterable by key or item

In short, it's like a dictionary where words and their meanings form an item. In a Map, a key is mapped to its value.

The most common implementation of the Map ADT is called Hash Map.

So, we can use a Hash Map to store the count of each element in the array.

Algorithm:

Iterate over all elements of the array
Update the count of the current element in hashmap
Iterate over keys of hashmap
If the value of the current key is 1 then return it

Code:

def approach3(nums):
    hashmap = {}

    for ele in nums:
        hashmap[ele] = hashmap.get(ele, 0) + 1

    for ele in hashmap:
        if hashmap[ele] == 1:
            return ele

Complexity analysis:

Time complexity: O(n + n*1) = O(2*n) = O(n) 
Space complexity: O(n), the size of hashmap will grow with the size of nums

Now that we've learned about this new ADT let's try to use Map to solve this in one loop.

Remember how Saitama, struck off an element when it's count increased from 1? Let's do that! We just have to remove the item from the Map.

Code:

def approach3_improved(nums):
    hashmap = {}

    for ele in nums:
        hashmap[ele] = hashmap.get(ele, 0) + 1

        if hashmap[ele] > 1:
            del hashmap[ele]

    keys = list(hashmap.keys())

    return keys[0]

Complexity analysis:

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

Approach 4

If you're decent at math then you may have observed that if the sum of the elements that occur twice is 'x' and the single number is 'y'

Sum of all elements = S1 = 2*x + y

But if we could somehow get the sum of all elements counted only once then

Sum of all unique elements = S2 = x + y

We need to find 'y', therefore

2*S2 - S1 = 2*(x + y) - (2*x + y)
2*S2 - S1 = 2*x + 2*y - 2*x - y
2*S2 - S1 = y
OR
y = 2*S2 - S1

Now that we've figured that out, all that is left to figure out a way to find the sum of unique elements in the array.

Enter Set

A Set is an abstract data type(ADT) with the following properties:

Add/Remove a list of unique objects

Test for existence of an object in the set

It should be iterable

The most common implementation of the Set ADT is called Hash Set or Set.

So, we can use a set to store unique elements of the array to get S2.

Algorithm:

Initialize empty set and variables setSum and normalSum to 0
Iterate over all elements of the array
If the element is not in the set then add to set and add value to setSum
Add value to normalSum
The required value is 2*setSum - normalSum

Code:

def approach4(nums):
    hashset = set()
    setSum = 0
    normalSum = 0

    for ele in nums:
        if ele not in hashset:
            hashset.add(ele)
            setSum += ele
        normalSum += ele

    ans = 2*setSum - normalSum
    return ans

Complexity analysis:

Time complexity: O(n) 
Space complexity: O(n), the size of hashset will grow with the size of nums

Approach 5

If you're a beginner then be warned because this approach is not normal.

Watch this video to get an idea of how this solution compares to what you've done until now. Our solutions until now are like the Cyborg: Genos and this solution is like the Bald guy: Saitama.

So, what is the killer move in this solution? In competitive programming, we often use bitwise operators to solve certain problems efficiently. It can be to store, remove or identify data or patterns.

In this problem, we will use the famous bitwise XOR Operator.

You can read up on it in the link above, but I'll list out the important properties of this operator w.r.t numbers here:

In the above properties A, B and C are numbers and the circle with a cross inside is the symbol used to denote the XOR operator. In programming, it is usually performed with the '^' symbol.

Now, since A^A = 0, 0^0 = 0 and 0^A = A and order doesn't matter

If we XOR all the elements in the array the result will be the single number because the numbers that occur twice will result in 0 and when 0 is XORed with the single number the result is the same.

Here's an example to simplify things:

Input: [6, 2, 4, 1, 3, 4, 1, 2, 6]

Result = 6 ^ 2 ^ 4 ^ 1 ^ 3 ^ 4 ^ 1 ^ 2 ^ 6

Since order doesn't matter in XOR, we can rewrite it as

Result = 6 ^ 6 ^ 4 ^ 4 ^ 2 ^ 2 ^ 1 ^ 1 ^ 3
       = ( 0 ) ^ ( 0 ) ^ ( 0 ) ^ ( 0 ) ^ 3
       = 0 ^ 3
       = 3

Now that it's clear we can do this in one loop, let's figure out how to solve it with no extra memory.

It's pretty simple, instead of storing the XORed result in a variable, we can use the elements of the array to store the XORed result until the corresponding index.

Algorithm:

Iterate from index 1 in the array
Assign array[i] = array[i] ^ array[i-1]
return array[length - 1]

Code:

def approach5(nums):

    for i in range(1, len(nums)):
        nums[i] = nums[i] ^ nums[i-1]

    return nums[-1]

Complexity analysis:

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

Summary

We've seen 5(6 overall) different approaches to solve this question.

Like I said the last approach is completely different but one pattern to note is that XOR helps in removing duplicate numbers as long as they come in even counts.

Here's a repl with a collection of all the above approaches. You can fork it and tweak it and try your own solutions.

I hope this post was useful, if you have any suggestions or doubts please comment below.

30-Day Leetcoding Challenge

Bharath Sriraam R R — Wed, 08 Apr 2020 12:52:07 +0000

LeetCode recently released a 30-Day Challenge where they will release a beginner-friendly programming problem every day starting from April 1st, which will be handpicked from their frequently asked interview questions along with 5 new problems.

They also have some nice rewards as incentives, but the condition is that you must solve every problem within 24 hours from the release time.

This is a very good challenge and opportunity if you're new to competitive programming or you want to warm up before solving hard problems.

I'm going to start a series of articles where I will post solutions. I encourage you to solve these problems by yourself, especially if you're a beginner in this field.

I've seen the first 7 problems and I'm sure that this challenge will be helpful in getting used to thinking differently and optimally.

Why this series?

In this series, you won't just find 1 optimal solution but rather a list of solutions that will progress from ineffective to optimal.

The reason I believe this is necessary is that it's difficult to think of an optimal solution in the first attempt and to truly become better you need to make mistakes and fix them by identifying bottlenecks, unnecessary work and duplicate work(BUD from Cracking the Coding Interview).

Don'ts and Do's

Usually, people try to search and learn things to do in order to get better at something but I have found that identifying things I do but I shouldn't be doing takes precedence.

When I first began competitive programming, I used to give up early and look at solutions, copy them into the editor, read it for a while and submit and feel good looking at that green tick ✅.

Then after a few competitions when I saw a question that seemed similar I would either try to remember the solution or search for my submission.

Pretty soon, I realized that this didn't help me grow, so I stopped copying solutions when I couldn't solve a question and tried to understand the algorithm behind a solution and then type it out myself.
Try to look at solutions written in languages other than your primary language because you may unconsciously try to remember code which is useless.

I use a pen and paper although I would suggest a notebook so that it can be a journal of your journey.

Dont's:

Don't search for solutions until trying to solve for a couple of hours
Don't just solve easy problems
Don't start by thinking of a solution in terms of Run time complexity or Space complexity

Do's:

Learn about popular data structures and algorithms 😬
Follow the BUD principle
Test your code against weird and edge cases 🤪
Identify patterns and note them
Try to simulate the problem in a real-world scenario and observe how you solve it (Surprisingly helps! but rarely)
Participate in many competitions

Summary

I'm too lazy to summarize so click here for the first post.
Have fun programming 👾

What React app(s) do I build to become really knowledgeable in it?

Bharath Sriraam R R — Tue, 25 Feb 2020 06:51:32 +0000

I've started building some projects in React but I only seem to be learning new css and JavaScript tricks but not anything in React.

So I was hoping to get some ideas or maybe specific features to implement that will make me use all sorts of lifecycle methods, hooks, redux/context and maybe stuff I still don't know about.

The suggestion can be fullstack, that'll be even better 😬. Thank you!