TWO SUM

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Solution 1: HashMap

  • We need to find 2 numbers a, b so that a + b = target.
  • We need a HashMap datastructure to store elements in the past, let name it seen.
  • The idea is that we iterate b as each element in nums, we check if we found a (where a = target - b) in the past.
    • If a exists in seen then we already found 2 numbers a and b, so that a + b = target, just output their indices.
    • Else add b to the seen.
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int b = nums[i], a = target - b;
            if (seen.containsKey(a)) return new int[]{seen.get(a), i}; // Found pair of (a, b), so that a + b = target
            seen.put(b, i);
        }
        return new int[]{};
    }
}

Complexity

  • Time: O(N), where N <= 10^4 is number of elements in the array nums.
  • Space: O(N)

Solution 2: Sort then Two Pointers

  • Since this problem require to output pair of indices instead of pair of values, so we need an array, let say arr to store their value with their respective indices.
  • Sort array arr in increasing order by their values.
  • Then use two pointer, left point to first element, right point to last element.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }
        Arrays.sort(arr, Comparator.comparingInt(o -> o[0])); // Sort arr in increasing order by their values.
        int left = 0, right = n - 1;
        while (left < right) {
            int sum2 = arr[left][0] + arr[right][0];
            if (sum2 == target)
                return new int[]{arr[left][1], arr[right][1]};
            if (sum2 > target)
                right -= 1; // Try to decrease sum2
            else
                left += 1; // Try to increase sum2
        }
        return new int[]{};
    }
}

Complexity

  • Time: O(N * logN), where N <= 10^4 is number of elements in the array nums.
  • Space: O(N)

Comments

Post a Comment

Popular posts from this blog

Java 8 : Find the number starts with 1 from a list of integers

  List<Integer> list = List. of ( 12 , 32 , 14 , 15 , 56 ); //Result->12,14,15 List<String> listString = list.stream().map(String::valueOf).collect(Collectors.toList()); List<String> result1 = listString.stream().filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result1-->" +result1); List<String> result2 = list.stream().map(x->x+ "" ).filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result2-->" +result2);
Read more

RDS vs Aurora DB

 1) Backtrack/Point in Time Restore (PITR) RDS Point in time restore is restore is supported, but it requires another RDS instance to be launched. Aurora Backtracks lets you quickly rewind the DB cluster to a specific point in time, without having to create another DB cluster. 2) Engine Options - Differences RDS - No concept of Global DB. Aurora - Global DB, Primary DB in one region and secondary DB in another region. 3) Compatibility with DB engines Aurora is compatible with two DBMSs namely PostgreSQL and MySQL. It is compatible with PostgreSQL 9.6.1 and MySQL 5.6. This means that you can run your existing database tools and applications on Aurora without any modifications.  On the other hand, Amazon RDS requires you to use AWS Database Migration Service to migrate from EC2-hosted or on-premises databases such as MySQL, PostgreSQL, MariaDB, Microsoft SQL Server, and Oracle. 4) Failover In RDS, Failover to read replica is done manually, which could lead to data loss. You can ...
Read more

Junit Mockito and Power Mockito

Mock vs Spy Both can be used to mock methods or fields. The difference is that  in mock, you are creating a complete mock or fake object while in spy, there is the real object and you just spying or stubbing specific methods of it . Mock vs InjectMock @Mock  creates a mock.  @InjectMocks  creates an instance of the class and injects the mocks that are created with the  @Mock  (or  @Spy ) annotations into this instance. Unit Testing Void Methods with Mockito and JUnit How to Test Void Methods  As we already know that our aim is to test void methods in a class. But it is also really important to understand why we test void methods.  Whenever we write unit test cases for any method, we expect a return value from the method. Generally, we use assert for checking if the method returns the value that we expect it to return, but in the case of void methods, they do not return any value. So how do we check if our method is functioning properly? Let’s...
Read more