Maximum single sell profit from stock

 Posted on April 30, 2015  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Problem Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit. OR Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[]. [Read More]
max  maxima  stock  divide and conquer  Dynamic Programming  DP  minima  array 

Find the largest subarray with sum of 0 in the given array

 Posted on April 17, 2015  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem An array contains both positive and negative elements, find the largest subarray whose sum equals 0. Example int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2} int output = {4, 6, 3, -9, -5, 1} of length 6 Solution Method 1 - Brute force This is simple. Will write later (incomplete) Method 2 - Storing the sum upto ith element in temp array Given an int[] input array, you can create an int[] tmp array where [Read More]
sub-array  Dynamic Programming  DP  incomplete  array  sum 

Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

 Posted on July 29, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Given an array arr[], find the maximum j – i such that arr[j] > arr[i]. Example Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Input: {1, 2, 3, 4, 5, 6} Output: 5 (j = 5, i = 0) Input: {6, 5, 4, 3, 2, 1} Output: -1 Solution Method 1 (Simple but Inefficient) [Read More]
Algorithms  kodeknight  sorting  array  distance 

Find the appropriate data structure

 Posted on April 10, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Lets see if you have solutions to the standard problems. Lets define the suitable data structures. Guess the data structues between the 2 data structures provided (in italics). Operations are Insert, DeleteMax, and DeleteMin. balanced tree or sorted doubly-linked list The balanced tree is better since all operations take O(log n) time. The sorted doubly-linked list is O(1) for DeleteMax and DeleteMin, but Insert is O(n); thus, the average time per operation is O(n). [Read More]
kodeknight  balanced trees  array  quiz 

LATIN SQUARE” and its implementation

 Posted on March 27, 2014  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem Understand Latin Square and its implementation Understanding the latin square “A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column” – Wikipedia. You can find the detail explanation of the properties of this Square here on Wikipedia In this article we will build a square to match the definition. [Read More]
kodeknight  2DArray  array  matrix 

Merge Overlapping Intervals

 Posted on March 26, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem Given a collection of intervals, merge all overlapping intervals. Input - Collection of intervals Output - Collection of mutually exclusive intervals after merging Example Given 1,31,3,2,62,6,8,108,10,15,1815,18, return 1,61,6,8,108,10,15,1815,18. Solution Method 1 - Brute force A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from list and merge the other into the first interval. [Read More]
kodeknight  merge  sorting  array  interval 

Find Local Minimum in an unsorted array with unique elements

 Posted on February 27, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

The pseudo / java code find only global minima and… Himadri Sarkar - Mar 0, 2014The pseudo / java code find only global minima and that too when no other local minima exist. I don’t think this problem can be solved in less than O(n) Hi Himadri, thanks for the comment. But I think the code is intended to give us local minima, and as we are apply binary search logic, it is possible in O(log n). [Read More]
kodeknight  local-minima  array  unsorted-array 

Find Local Minimum in an unsorted array with unique elements

 Posted on February 27, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem: Given an array ‘a’ of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] > a[i] < a[i+1]. Examples: a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs Solution: **Brute force ** Go through each element 3 tuples, and compare them. [Read More]
kodeknight  local-minima  array  unsorted-array 

How to find max. and min. in array using minimum comparisons?

 Posted on February 14, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem : Given an array of integers find the max. and min. using minimum comparisons. Solution Method 1 (Naive) - Iterate through the array, and update min and max pointers 1\. Iterate through the array, select element a 2\. Update min by comparing (min, a) 3\. Update max by comparing (max, a) Number of comparison here will be ~2N, if N is number of element. Time complexity will be O(n) though. [Read More]
max  kodeknight  browserstack  minmax  array  unsorted-array  min