Maximum Profit from given array of Stock Prices - Programming Problem

$\mathtt{REFERENCE}$ @ Interve Cake

Problem Definition

You are given an array of Stock Prices. Index of the array represents the time corresponding to a price. Smaller index represents past time and larger index represents future time.

Now you need to write a method that takes the array as an input and returns the best profit that could be made by buying 1 stock and selling 1 stock.

Example

  int[] stockPrices = new int[] {15, 5, 10, 25, 55, 1};

  getMaxProfit(stockPrices); // returns 50 (buy at $5 and sell at $55)

    

Only the stock bought at past can be sold in the future. So the time difference must be at least 1 for conducting the transaction.

Brute Force Solution

Brute Force solution would be to consider every valid pair and keep updating the maximum profit that can be made.

  /**
   * Brute Force Approach to calculate the profit
   * @param stockPrices input stock prices
   * @return max profit
   */
  public static int getMaxProfit(int[] stockPrices) {
    int maxProfit = Integer.MIN_VALUE;

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

    return maxProfit;
  } // getMaxProfit

    

Time Complexity

The outer loop runs for all the prices i.e. $n$ times $n$ being the number of stock prices.

For the first outer loop, the inner loop runs for $n-1$ times
For the second outer loop, the inner loop runs for $n-2$ times
For the third outer loop, the inner loop runs for $n-3$ times and so on until 0.

So, the two loops run for $(n-1) + (n-2) + (n-3) + ...... + 2 + 1 + 0 \approx n^2$ times. Operations inside the loops are constant time operations.

$\therefore$ Total Time complexity is ${\cal O}(n^2)$. The space complexity is ${\cal O}(1)$.

Linear Time Solution

The problem can be solved in linear time by traversing the array only once. For each item traversed, we store the minimum value of the stock seen so far and update the maximum profit greedily.

  /**
   * Linear Time solution to find the max profit
   * @param stockPrices input stock prices
   * @return max profit
   */
  public static int getMaxProfit(int[] stockPrices) {
    int maxProfit = Integer.MIN_VALUE;
    int minPrice = stockPrices[0];

    for (int i = 1; i < stockPrices.length; i++) {
      int profit = stockPrices[i] - minPrice;
      if (maxProfit < profit) {
        maxProfit = profit;
      }

      if (minPrice > stockPrices[i]) {
        minPrice = stockPrices[i];
      }

    }
    return maxProfit;
  } // getMaxProfit

    

Time Complexity

In this solution, the stock prices are accessed only once. And for the stock price the processing is constant time.

$\therefore$ The overall time complexity is ${\cal O}(n)$. The Space complexity remains ${\cal O}(1)$.

Implementation

---

---

---

Electronics Shop - HackerRank Problem

Find the problem definition @ HackerRank

Brute-Force Solution

Using the Brute-Force method, this problem can be solved by considering every possible pairs. If the considered pair gives better result (i.e > max) and satisfies the constraints (i.e. <= s), then we select current pair as the solution. Result is returned after all the pairs have been considered.

  /**
   * Brute Force Solution
   * @param s
   * @param keyboards
   * @param drives
   * @return
   */
  public int getMoneySpent(int s, int[] keyboards, int[] drives) {
    int max = -1;
    for (int i = 0; i < keyboards.length; i++) {
      for (int j = 0; j < drives.length; j++) {
        int amount = keyboards[i] + drives[j];
        if (amount > max && amount <= s ) {
          if (max == s) return max;
          max = amount;
        }
      }
    }
    return max;
  }    
    

Time Complexity

Time Complexity of this solution depends upon the number of pairs considered. Since there are $n\ keyboards$ and $m\ drives$, total of $n \times m$ pairs are considered. Processing time for each pair, as we can see in the code, is constant time operation ${\cal O}(1)$. $\therefore$ The time complexity of this solution is ${\cal O}(n \times m)$. The space complexity is ${\cal O}(1)$ since we haven't use any extra data structure to hold inputs.

Better Solution

The problem could be optimized to solve in better time complexity. We can Sort one of the array and iterate through other array. While iterating through the other array, we apply the Binary Search on the sorted array to obtain the best pair. In order to keep the complexity low (Do the maths on your own ), I am going to sort the array with lower number of elements and iterate over the other one.

/**
   * Computes using Binary Search
   * @param keyboards
   * @param drives
   * @param s
   * @return
   */
  public int getMoneySpent(int[] keyboards, int[] drives, int s) {
    int max = -1;
    int[] larger = keyboards.length > drives.length ? keyboards : drives;
    int[] smaller = keyboards.length > drives.length ? drives : keyboards;

    Arrays.sort(smaller); // O(k logk)

    for (int i = 0; i < larger.length; i++) {  // O(n)
      if (larger[i] < s) {
        int pair = search(smaller, s - larger[i], 0, smaller.length); // O(logk)
        if (pair == -1) continue;
        if (max < smaller[pair] + larger[i]) {
          max = smaller[pair] + larger[i];
        }
      }
    }
    return max;
  } // getMoneySpent
  
  //----------------------------------------------------------------------------------

  /**
   * Searches the best pair using Binary Search
   * @param in
   * @param item
   * @param lo
   * @param hi
   * @return
   */
  public int search(int[] in, int item, int lo, int hi) {
    if (item < in[lo]) return -1;
    while (hi - lo > 1) {
      int midIdx = (lo + hi) / 2;
      if (item == in[midIdx]) return midIdx;
      else if (item > in[midIdx]) {
        lo = midIdx;
      } else {
        hi = midIdx;
      }
    }
    return lo;
  } // search

    

Time Complexity

Time Complexity of the solution depends upon the sorting of smaller array, iteration of larger array and the binary search on the sorted array.

Let, $n =$ Number of Elements in the larger array
       $k =$ Number of Elments in the smaller array

Then,

1. Time Complexity of Sorting = ${\cal O})(k\ logk)$
2. Time Complexity of iteration = ${\cal O}(n)$
3. Time Complexity of Binary Serach = ${\cal O}(logk)$

$\therefore$ The overall Time Complexity is ${\cal O}(k\ logk + n\ logk) \approx {\cal O}(n\ logk)$. The Space Complexity is ${\cal O}(1)$

---

---

---