Amazon Interview question from leetcode coding problem 1

Hi, This is Shubham Mishra from India,  this is the part of Ruby on Rails exploration journey.  In this post we will discuss about the leetcode problem and its both worst and best case solution asked in Amazon interview process and I am sure you will get excited to make your hands dirty with those code, so why to wait let's get started...

Problem Statement:

Return the indices of the two numbers such that they add up to target given an array of integers nums and an integer target. You may presume that each input would have exactly one solution, and you may not use the same element twice.

The input array nums can be assumed to not be sorted, but you are free to return the solution in any order.

Example:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: nums[0] + nums[1] = 2 + 7 = 9, so [0, 1] is the correct answer.

Here is the function signature in Python to help you get started:


The problem is to find two indices in an array of integers nums whose corresponding values add up to a given target. Here are 2 solutions to the problem, with diffrent time complexities:

1. Brute Force Solution: A brute-force approach would be to use two nested loops to compare each pair of numbers in the array and see if they correspond to the same object. The time complexity of this would be O(n^2), where n is the length of the input array.



2. Hash Map Solution: A better solution is to use a hash map to store the complement of each element in the array (i.e., the difference between the target and the element), and then check if each subsequent element is present in the hash map. This would have a time complexity of O(n), where n is the length of the input array.


here is a step-by-step explanation of the second solution for the problem:

1. Create an empty hash map to store the complement of each element in the array.

2. Loop through each element in the array nums along with its index i.

3. Compute the complement of the current element as complement = target - num, where target is the given target sum and num is the current element in the array.

4. Check if the complement is already present in the hash map. If yes, then return the indices of the two elements that add up to the target. The index of the complement can be retrieved from the hash map, and the current index i can be used as the index of the current element. For example, return [map[complement], i].

5. If the complement is not present in the hash map, then add the current element and its index to the hash map. This is done so that the hash map can be used to quickly look up the complement of any subsequent elements in the array.

6. If no such pair of elements is found that add up to the target, then return nil or any other value that indicates that no solution was found.

The key insight of this solution is to use a hash map to store the complement of each element, which allows for constant time lookups. This reduces the time complexity from O(n^2) in the brute force solution to O(n) in this solution.

The worst-case time complexity for both solutions is O(n^2) and O(n) respectively. The best-case time complexity for both solutions is O(1), when the target is already found in the input array. The hash map solution is generally faster and more efficient than the brute force solution, especially for larger input arrays.

You can explore my previous blog: Shell script to open multiple chrome windows with auto close command

Or you can explore my other blogs too here,

Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.

Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.

My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.

Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.

Liked my blogs, wanna to connect:

LinkedIn  |  GitHub  |  HackerEarth  |  ResearchGate  |  Twitter  |  Facebook  |  StackOverflow

Thanks for reading this post, Have a good day :)