DEV Community: Abhi Agarwal

Longest Common Prefix

Abhi Agarwal — Sat, 22 Aug 2020 04:50:26 +0000

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Solution:

The requirement here is to find longest common prefix amongst an array of strings.

There are many approaches to this problem but the one that I am going to discuss here uses Trie to store the array of strings and then scan the trie to get the longest common prefix.

To know more about Trie, you can visit here.

Algorithm:

1) Store each string from the array of strings in Trie.

2) Get the deepest Trie Node such that all the nodes from the root of the trie to that node has only one children.

Link to Code

Space Complexity: O(n) where n is the number of unique characters in the array of string.

Time Complexity: O(n) for building the Trie (n is the number of unique characters in the array of string) and O(m) for finding the prefix (where m is the length of the prefix).

Remove Duplicates From Sorted Array

Abhi Agarwal — Fri, 21 Aug 2020 03:59:11 +0000

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.

It doesn't matter what you leave beyond the returned length.
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.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by >the caller.
// using the length returned by your function, it prints the >first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

Solution:

The requirement here is to remove all the duplicates from the array such that each element occurs only once.

To solve this problem, we can use two-pointer approach here. We will have a fast pointer called 'i' and a slow pointer called 'j'. We will compare each element with the element a location 'j'. If we encounter an element which is greater than the element at 'j' then we will add that element to position 'j+1' and update 'j'.

Github Link Link

Blog Link Link

Time Complexity: O(n)

Space Complexity: O(1)

Two Sum

Abhi Agarwal — Fri, 21 Aug 2020 00:34:51 +0000

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

Since for each element 'x' present in the array, we will have to check whether a number 'y' exists in the array such that sum of two numbers is target and return indices of the number.

We can also say that, for any element 'x' present in the array , find a number 'target-x' which is also present in the array.

One approach to the problem is to scan the complete array for finding number 'target-x' for each element 'x'.

Another approach is to use dictionaries. For each element 'x' in the array, check whether the dictionary contains element 'target-x'.

So here, first we will scan the complete array to store the elements of the array in the dictionary with element as the key and index of the element as the value.

Here is the link to my github repo that contains the solution Link

Time Complexity: O(n)

We are checking for map[nums[i]]>=2 to avoid fetching the same element twice.

For Example:

Given nums = [2, 7, 11, 15], target = 4,

If we are trying to find complement of 2 which is 2 for target 4 >then dictionary will still return true since the element is >present but it's not an actual solution to the problem.

Link to my blog: Link