50 DSA-Questions: #1, #2

#1. Two Sum

Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to the 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.

public class Exercise1 {
    private final Integer[] ARRAY = {0, 1, 2, 4, 6, 7, 8, 9, 15};
    private final int TARGET = 10;

    private void solve() {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = Arrays.asList(ARRAY);
        for (int element : list) {
            map.put(element, list.indexOf(element));
        }
        for (int element : list) {
            int key = TARGET - element;
            if (map.containsKey(key)) {
                System.out.println("[" + map.get(element) + "," + map.get(key) + "]");
                map.remove(element);
                map.remove(key);
            }
        }
    }

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

#2. Best Time to Buy and Sell Stock

You are given an array of prices where prices[i] is the price of a given stock on an i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

public class Exercise2 {
    // private final Integer[] PRICES = {7,1,5,3,6,4}; // prices on i-th day
    private final Integer[] PRICES = {5,2,21,8,4,2,12,5,9,19,1,13}; // prices on i-th day

    // Return max profit (buy min possible & sell max possible)
    private void solve() {
        int[] min = new int[PRICES.length];
        min[0] = PRICES[0];
        for (int i = 1; i < PRICES.length; i++) {
            min[i] = PRICES[i] < min[i-1] ? PRICES[i] : min[i-1];
        }

        int[] max = new int[PRICES.length];
        max[PRICES.length - 1] = PRICES[PRICES.length - 1];
        for (int i = PRICES.length - 2; i > 0; i--) {
            max[i] = PRICES[i] > max[i+1] ? PRICES[i] : max[i+1];
        }

        int maxProfit = 0;
        for (int i = 1; i < PRICES.length; i++) {
            int profit = max[i] - min[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }

        System.out.println("max profit = " + maxProfit);
        // O(n)
    }

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