Skip to content

Latest commit

 

History

History
72 lines (41 loc) · 3.47 KB

twoSum.md

File metadata and controls

72 lines (41 loc) · 3.47 KB

Problem statement: Given an array of integers nums and an integer target, return the two indices i and j such that nums[i] + nums[j] == target and i != j.

Note: You may assume that each input has exactly one pair of indices i and j that satisfy the two sum conditions. Return the indices pair in any order.

Examples:

Example 1:

Input: nums = [3, 4, 9, 14], target=12 Output: [0, 2]

Example 2:

Input: nums = [5, 7, 4, 7], target=14 Output: [1, 3]

Example 3:

Input: nums = [7, 1, 13, 1], target=10 Output: []

Example 4:

Input: nums = [-5, -4, -3, -1, -2], target=-10 Output: []

Approach1 algorithmic Steps This problem is solved in a one pass with the help of map data structure. The algorithmic approach can be summarized as follows:

  1. Add a preliminary check two verify the length of input array and return an empty array if the length is less than 2.

  2. Initialize an index map(i.e, indexMap) to store the current iteration number as key and index as value.

  3. Iterate over the input array using index pointer until the end of the array.

  4. Find the complement by subtracting the target and current number. If the complement already exists in the map, return the indices of complement and current number as output.

  5. If the complement doesn't exist in our indexMap, just add the current number and its index to the map.

  6. Repeat steps 5–6 until there are indices present to meet the target or the index pointer reaches the end of the array.

  7. Return an empty array if there are no indices present in an array.

Time and Space complexity: This algorithm has a time complexity of O(n) because we are traversing the array only once. Remember that checking an element existence in a map or adding an element to a map takes a constant time(i.e, O(1)).

Also, it takes requires space complexity of O(n) because we are using map data structure. In the worst case, when there are no indices, you need to insert all the elements of an array into map.

Approach2 algorithmic Steps This problem is solved in a one pass with the help of object. The algorithmic approach can be summarized as follows:

  1. Add a preliminary check two verify the length of input array and return an empty array if the length is less than 2.

  2. Initialize an index object(i.e, indexObj) to store the current iteration number as name and index as value.

  3. Iterate over the input array using index pointer until the end of the array.

  4. Find the complement by subtracting the target and current number. If the complement already exists in the object, return the indices of complement and current number as output.

  5. If the complement doesn't exist in our indexObj, just add the current number as value and its index as property name to the object.

  6. Repeat steps 5–6 until there are indices present to meet the target or the index pointer reaches the end of the array.

  7. Return an empty array if there are no indices present in an array.

Time and Space complexity: This algorithm has a time complexity of O(n) because we are traversing the array only once. Remember that checking an element existence in an object or adding an element to an object takes a constant time(i.e, O(1)).

Also, it takes requires space complexity of O(n) because we are using object. In the worst case, when there are no indices, you need to insert all the elements of an array into map.