Two Sum Problem

Problem description:

Given an array of integers, find two numbers such that they add up to a specific target number.

Your function should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

There exist a very obvious quadratic solution, you would just need to loop through the array and for each i element loop from i +1 to n to look for the number which gives you a sum so that array[i] + array[j] = target. This approach works just fine but the problem is that it’s too slow, it runs in quadratic time O(n^2), could we do it better? Yes.

An optimized solution is to use an additional data structure which allows us to keep track of each number that we have and also its index, for this task we could use a HashMap which offers a constant time look-up operation, so we just need to loop the array once to store the elements and their corresponding indices in our HashMap and then loop through the array again and for each element i just check if hashmap.containsKey(target – array[ i ]). Here is the working solution implemented in Java:


public int[] twoSum(int[] numbers, int target) {
        
    HashMap<Integer, Integer> indexes = new HashMap<Integer, Integer>();
        
    for(int i = 0; i < numbers.length; ++i) {
        indexes.put(numbers[i], i);
    }
            
    for(int i = 0; i < numbers.length; ++i) {
        if(indexes.containsKey(target - numbers[i])) {
            return new int[]{i + 1, indexes.get(target - numbers[i]) + 1};
        }
     }
    return null;
}

This solution is much faster than the first approach, this runs in linear time (considering that HashMap look-up operation runs in constant time).

Advertisements

Check if a string has all unique characters without using extra space

Given a string, check if all its elements are unique, it means, there are no repeated characters.

example:

HELLO -> not all its characters are unique since character ‘l’ appears twice.

WORLD -> has all unique characters

This problem has many possible solutions, and to make it more interesting let’s suppose we are not allowed to use any extra data structure (a few extra variables are allowed but an entire copy of the array is not).

Solution.

Approach 1: Quadratic solution

The idea is to loop through the string an compare each element to the ones that we know they are unique so far, it could be done with the code below:

static boolean checkUniqueCuadratic(char arr[])
{
    int point = 0; //all elements before this point are unique for sure

    for(int i = 0; i < arr.length; ++i) // for each element, we are gonna compare to each unique element
    {
        char c = arr[i];

        for(int j = 0; j < point; ++j)
        {
            if(c == arr[j]) {
                return false;
            }
        }
        ++point; // at this time we now have a new unique element
    }
    return true;
}

Note that the solution above runs in quadratic time O(n^2) since it has two nested loops. We could probably just keep a data structure that allows us to keep of which elements we have visited and then just check if the ith element is within our helper data structure in just one loop, but remember we are not allowed to use any additional data structure.

Approach 2: “linearithmic” solution (n log n in time complexity)

Another good approach and actually faster is to sort the string by using any in place sorting algorithm which guarantees n log n in time complexity (like quicksort) and then just loop through the string and check if the next element equals the current element. The code below shows the implementation of this approach:


import java.util.*;

public class UniqueChars
{
    public static void main(String... args)
    {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNextLine())
        {
            char line[] = sc.nextLine().toCharArray();
            quicksort(line, 0, line.length - 1);// sort the string by using quicksort
            System.out.println(checkUnique(line));
        }
    }

    static boolean checkUnique(char arr[])
    {
        for(int i = 0; i < arr.length - 1; ++i)
            if(arr[i] == arr[i + 1])
                return false;

        return true;
    }

    /*
       Basic quicksort implementation
    */
    static void quicksort(char array[], int a, int b)
    {
        if(b - a < 1)
            return;

        int pivot = a;
        int i = a + 1;
        int j = b;

        while(i < j)
        {
            while(array[i] < array[pivot] && i < b) i++;
            while(array[j] > array[pivot] && j > a) j--;

            if(i < j)
                interchange(array, i, j);
        }
        interchange(array, pivot, j);

        quicksort(array, a, j - 1);
        quicksort(array, j + 1, b);
    }

    static void interchange(char arr[], int a, int b)
    {
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

You have any comment/suggestion/question? please let us know!!