Tuesday, January 10, 2012

Best time to buy and sell stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.
http://www.geeksforgeeks.org/maximum-difference-between-two-elements/
http://articles.leetcode.com/best-time-to-buy-and-sell-stock/

Variation 1: Buying and Selling Multiple Times
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
http://www.geeksforgeeks.org/stock-buy-sell/

Variation 2: Best Time to Buy and Sell Stock with Cooldown
https://shirleyisnotageek.blogspot.in/2016/06/best-time-to-buy-and-sell-stock-with.html

Variation 3: Minimum difference between any two numbers
There is a given array, we have to find the minimum difference between any two numbers of the array in best time complexity
http://www.geeksforgeeks.org/find-minimum-difference-pair/

Strategy:O(n)
We need to use 3 pointers.min index,buy index,sell index
To solve this problem efficiently, you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

Code:
void getBestTime(int stocks[], int sz, int &buy, int &sell) {
  int min = 0;
  int maxDiff = 0;
  buy = sell = 0;
  for (int i = 0; i < sz; i++) {
    if (stocks[i] < stocks[min])
      min = i;
    int diff = stocks[i] - stocks[min];
    if (diff > maxDiff) {
      buy = min;
      sell = i;
      maxDiff = diff;
    }
  }
}

Variation 3:
Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[].

Solution for Variation 1:Two Pointer Method

#include <stdio.h>
#include <algorithm>
#include <limits.h>

/*a is array, n is size of array,
b and c are the 2 numbers
between which we have to find min distance.*/
int minDist(int a[], int n, int b, int c) {

    int  ret = INT_MAX, cur = -1;

    while(n--) {
        if(a[n] == b || a[n] == c) {
            if(cur != -1 && a[cur] != a[n]) {
                ret = std::min(ret, cur - n);
            }
            cur = n;
        }
    }
    return ret;
}

int main() {

    int a[] = {1, 2, 10, 2, 3, 5, 2, 1, 5};
    printf("%d\n", minDist(a, sizeof(a)/sizeof(int), 2, 5));
    return 0;
}

Posted by at 5:34 AM
Labels: , ,

4 comments:

  1. SudJanuary 14, 2012 at 10:16 AM

    Solution for MAIN Question:

    If list is sorted then the the two numbers with minimum difference would always be consecutive so we can start from first and take two numbers; find the difference and assume that this is the min diff. finally take another two numbers and find the minimum diff between them and update the min diff.

    This would be O(n) if array is sorted; else first sort the array and then use this method so O(n logn).

    ReplyDelete
    Replies
    1. SudOctober 8, 2012 at 10:12 PM

      Two pointer Approach:
      1) Traverse array from left side and stop if either x or y are found. Store index of this first occurrence in a variable say prev
      2) Now traverse arr[] after the index prev. If the element at current index i matches with either x or y then check if it is different from arr[prev]. If it is different then update the minimum distance if needed. If it is same then update prev i.e., make prev = i.

      Code:
      #include < stdio.h >
      #include < stdlib.h >
      #include < limits.h >

      #define MIN(a, b) ((a>b)?(b):(a))

      int minDistance(int* arr, int len, int x, int y)
      {
      int prevIndex = -1;
      int min = INT_MAX;
      int i=0;
      int first;
      int second;
      int distance;


      for(i=0; i < len; i++)
      {
      if((arr[i] == x) || (arr[i] == y))
      {
      //first time encounter with x or y
      //'first' stores either x or y, depending on
      //which is encountered first
      if(prevIndex == -1)
      {
      first = (arr[i]==x)?x:y;
      second = (arr[i]==x)?y:x;
      prevIndex = i;
      }
      else
      {
      //if arr[i] is same as 'first', reset prevIndex
      if(arr[i] == first)
      prevIndex = i;
      //if arr[i] is different from 'first', calculate distance
      else
      {
      distance = i - prevIndex;
      prevIndex = i;
      min = MIN(min, distance);

      //swap first and second
      int temp = first;
      first = second;
      second = temp;
      }
      }
      }
      }
      return min;
      }

      int main()
      {
      int arr[] ={2, 5, 4, 6, 6, 7, 5, 1, 4};

      int len = sizeof(arr)/sizeof(int);

      printf("MIN DISTANCE: %d\n", minDistance(arr, len, 4, 5));
      return 0;
      }

      Delete
  2. SudJanuary 14, 2012 at 10:19 AM

    Code For Variation 1:

    int main()
    {
    int arr[]={2,3,7,2,5,9,5};
    int i,j,size, prev_index, min_dist;
    size = sizeof(arr)/sizeof(arr[0]);
    int x, y;
    x = 2; y = 5;
    min_dist = 65535;
    for(i=0;i < size;i++)
    {
    if(arr[i] == x || arr[i] == y)
    {
    prev_index = i;
    break;
    }
    }
    for(;i < size;i++)
    {
    if(arr[i] == x || arr[i] == y)
    {
    if(arr[prev_index] != arr[i] && (i - prev_index) < min_dist)
    {
    min_dist = i - prev_index;
    prev_index = i;
    }
    else
    prev_index = i;
    }
    }
    printf("%d\n", min_dist);
    return 0;
    }

    ReplyDelete
  3. Shivam KumarDecember 4, 2015 at 11:25 AM

    Very Nice ... Must visit more Java Example

    ReplyDelete

Subscribe to: Post Comments (Atom)