Data Structures And Algorithams

Single Transaction (Buy Once, Sell Once),

You can only buy once and sell once.

The goal is to maximize profit.

Approach:

• Track the minimum price seen so far.
• At each step, calculate profit = currentPrice - minPriceSoFar.
• Keep updating the maximum profit.

public class BestTimeBuySell {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println("Max Profit (Single Transaction): " + maxProfit(prices));
    }
}

2. Multiple Transactions (Buy and Sell Many Times)

You can buy and sell multiple times, but you must sell before buying again. The goal is to maximize total profit.

Approach:

• Add up every increase (prices[i] > prices[i-1]).
• This works because each rise can be treated as a buy-sell pair.

public class BestTimeBuySellII {
    public static int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println("Max Profit (Multiple Transactions): " + maxProfit(prices));
    }
}

String Permutations

Approach

1. Fix one character at a time.
2. Swap it with each possible position
3. Recursively permute the remaining substring.
4. Backtrack (swap back) to restore the original string.

public class StringPermutation {
    // Utility function to swap characters in a string
    private static String swap(String str, int i, int j) {
        char[] chars = str.toCharArray();
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }

    // Recursive function to generate permutations
    public static void generatePermutation(String str, int start, int end) {
        if (start == end - 1) {
            System.out.println(str);
        } else {
            for (int i = start; i < end; i++) {
                str = swap(str, start, i);
                generatePermutation(str, start + 1, end);
                str = swap(str, start, i); // backtrack
            }
        }
    }

    public static void main(String[] args) {
        String str = "ABC";
        generatePermutation(str, 0, str.length());
    }
}

Java subset Problem-string problem

• Number of subsets = 2n, where n is the length of the string.
• For "ABC", 23=8 subsets.
• This approach works for any string length.

public class SubsetsOfString {
    // Recursive function to generate subsets
    public static void generateSubsets(String str, String current, int index) {
        if (index == str.length()) {
            System.out.println(current);
            return;
        }

        // Option 1: Exclude current character
        generateSubsets(str, current, index + 1);

        // Option 2: Include current character
        generateSubsets(str, current + str.charAt(index), index + 1);
    }

    public static void main(String[] args) {
        String str = "ABC";
        System.out.println("All subsets of " + str + ":");
        generateSubsets(str, "", 0);
    }
}

Trap rainwater problem:

public class TrappingRainWater {
    public static int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // Fill leftMax
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }

        // Fill rightMax
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }

        // Calculate trapped water
        int trapped = 0;
        for (int i = 0; i < n; i++) {
            trapped += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return trapped;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println("Trapped water: " + trap(height));
    }
}