50 DSA-Questions: #8, #9

#8. Search in Rotated Sorted Array

Given the array nums after the possible rotation and an integer target, return the index of the target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity.

public class Exercise8 {
    private final int TARGET = 0;
    private final int[] ARRAY = {4,5,6,7,0,1,2}; // index = 4
    // private final int[] ARRAY = {10,12,0,4,5,7}; // index = 2
    // private final int[] ARRAY = {0,7,8,9,10}; // index = 0
    // private final int[] ARRAY = {3,4,6,7,8,9,0}; // index = 6
    // private final int[] ARRAY = {7, -6, -3, -2, -1, 0, 5}; // index = 5

    private void find(int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex || leftIndex + 1 == rightIndex) { // one or two elements left
            int index = ARRAY[leftIndex] == TARGET ? leftIndex : (ARRAY[rightIndex] == TARGET ? rightIndex : -1);
            System.out.println("Index = " + ((index > -1) ? index : "N/A"));
            return;
        }

        int mid = leftIndex + (rightIndex - leftIndex) / 2;

        if (ARRAY[leftIndex] <= ARRAY[mid] && ARRAY[leftIndex] <= TARGET && ARRAY[mid] >= TARGET) { // search in left array
            find(leftIndex, mid);
            return;
        }

        if (ARRAY[mid+1] <= ARRAY[rightIndex] && ARRAY[mid+1] <= TARGET && ARRAY[rightIndex] >= TARGET) { // search in right array
            find(mid+1, rightIndex);
            return;
        }

        if (ARRAY[leftIndex] > ARRAY[mid] && TARGET <= ARRAY[mid]) {
            find(leftIndex, mid); // search in left array
            return;
        }

        find(mid+1, rightIndex); // search in right array
    }

    private void solve() {
        find(0, ARRAY.length - 1);
    }

    public static void main(String args[]) {
        new Exercise8().solve();
    }
}

#9. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

public class Exercise9 {
    // private final Integer[] NUMS = {-1,0,1,2,-1,-4}; // triplets [[-1,-1,2],[-1,0,1]]
    private final Integer[] NUMS = {1, 2, -3, 2, -4, 1, 3, 1, -2}; // triplets [[1,2,-3],[2,2,-4],[1,1,-2],[1,-4,3]]
    private final int TARGET_SUM = 0;

    private List<Pair<Integer, Integer>> twoSum(int targetSum, int indexThird) {
        List<Integer> list = Arrays.asList(NUMS);
        List<Pair<Integer, Integer>> result = new ArrayList<>();

        for (int i=0; i<list.size(); i++) {
            if (i == indexThird) {
                continue; // duplicate
            }

            final int element = list.get(i); // to the left
            int key = targetSum - element; // to the right
            if (list.indexOf(element) == list.lastIndexOf(key) || indexThird == list.lastIndexOf(key)) {
                continue; // duplicate
            }

            if (list.contains(key)) {
                result.add(new Pair<>(element, key));
            }
        }
        return result;
    }

    private void solve() {
        Set<String> result = new HashSet<>();
        for (int i=0; i<NUMS.length; i++) {
            int thirdElement = TARGET_SUM - NUMS[i];
            final int element = NUMS[i];
            List<Pair<Integer, Integer>> twoSums = twoSum(thirdElement, i);
            if (!twoSums.isEmpty()) {
                twoSums.forEach(twoSum -> {
                    String label = "[" +
                            getMinValue(element, twoSum.getKey(), twoSum.getValue()) + ","  +
                            getMidValue(element, twoSum.getKey(), twoSum.getValue()) + ","  +
                            getMaxValue(element, twoSum.getKey(), twoSum.getValue()) + "]";
                    result.add(label);
                });
            }
        }
        System.out.println(result);
    }

    private int getMidValue(int a, int b, int c) {
        return Math.max(Math.min(a,b), Math.min(Math.max(a,b),c));
    }

    private int getMaxValue(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    private int getMinValue(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    public static void main(String args[]) {
        new Exercise9().solve();
    }
}