Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
PS: Array does not have to be sorted, works also for unsorted arrays, for example: [2, 3, 10, 6, 4, 8, 1] where max diff = 10 - 2 = 8
public class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int min_val = Integer.MAX_VALUE;
int max_diff = 0;
for(int i = 0; i < n; i++) {
if (prices[i] < min_val)
min_val = prices[i];
int diff = prices[i] - min_val;
if (diff > max_diff)
max_diff = diff;
}
return max_diff;
}
}
A simple solution in C with linear time complexity
The given array is A = {10, 3, 6, 8, 9, 4, 3}
int max = 0;
int res = 0;
for(int i = n - 1; i >= 0; i--)
{
if(A[i] > max)
max = A[i];
int tempdiff = max - A[i];
if(tempdiff > res)
res = tempdiff; // this gives the maximum difference in the array
}
In the example, if I'm understanding the question properly, the best possible solution is 6, the difference between the first element and the last element of the array.
More generally, if we iterate forward from an element with value x, any number we encounter that is greater than x cannot be the min part of the solution, since we can always use x instead.
Iterate through all the elements, at each step checking the difference between the min and the element, updating the best solution found so far if necessary. If a new min is found update the min
Identify the max-diff from the back and iterate till front. It roughly looks like below
int maxdiff;
int smallest = arr[n-1];
int largest = arr[n-1];
for(int i=n-2; i>=0; i--)
{
int currentMaxDiff = Max(abs(arr[i]-smallest), abs(arr[i]-largest));
if(currentMaxDiff>maxdiff)
{
maxdiff=currentMaxdiff;
}
if(arr[i]<smallest)
{
arr[i] = smallest;
}
if(arr[i]>largest)
{
arr[i] = largest;
}
}
MaxDiff should have the maximum difference at the end.
This is not correct since you don't account for 'given the second element comes after the first'
Your solution delivers 2 for {3, 2, 1} but it should really be -1
Actually I got confusion with your answer as per your example 1-3 can produce -2 but you mentioned as it should be -1 (1-2) pls explain.
Given an array, find the maximum difference between two array elements -->given the second element comes after the first.<--
I think this is a typical dynamic programming question. Using following formula to get:
D[i] = D[i-1] + (A[i] - A[i-1])
D[0] = 0
Where A[] is the input array and D[] is the difference array that we calculate from input A[].
For example, A[] = 1, 5, 8, 7, 9, -5, 15, 21
Calculate D[] = 0, 4, 7, 6, 8, -6, 14, 20
go through D[] to find the maximum difference is 20, which is really O(n) complexity
one pass
public class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int min_val = Integer.MAX_VALUE;
int max_diff = 0;
for(int i = 0; i < n; i++) {
if (prices[i] < min_val)
min_val = prices[i];
int diff = prices[i] - min_val;
if (diff > max_diff)
max_diff = diff;
}
return max_diff;
}
}
private static void MaximumDiff()
{
int[] arr = { 7, 6, 15, 4, 3, 21, 1 };
int min = arr[0];
int max = arr[1];
int diff = max - min;
bool minchanged = false;
bool maxchanged = false;
for (int i = 1; i < arr.Length - 1; i++)
{
minchanged = false;
maxchanged = false;
if (arr[i] < min)
{
min = arr[i];
minchanged = true;
}
if (arr[i + 1] > max)
{
max = arr[i + 1];
maxchanged = true;
}
if (minchanged && maxchanged && (max - min) > diff)
diff = max - min;
if (maxchanged && (max - min) > diff)
diff = max - min;
}
Console.WriteLine(diff);
}
public class FindDifference {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}
}
public class FindDifference {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}
}
This works - O(n) solution.
int maxDifference(int [] array) {
if (array.length <= 1) {
System.out.println("Size of the array should be greater than 1");
System.exit(1);
}
int currentMaxDiff = array[1] - array[0];
int currentMin = array[0] < array[1] ? array[0] : array[1];
for (int i = 2; i < array.length; i++) {
if (array[i] - currentMin > currentMaxDiff) {
currentMaxDiff = array[i] - currentMin;
}
if (currentMin > array[i]) {
currentMin = array[i];
}
}
return currentMaxDiff;
}
dp ?
public int findMaxDiff (int [] A){
int [] left = new int [A.length] ;
int leftMax = Integer.MIN_VALUE ;
for (int i = 1 ; i < A.length ; ++i) {
if (A[i] > A[i - 1]) left[i] = A[i] - A[i - 1] + left[i - 1];
leftMax = Math.max(leftMax, left[i]);
}
int rightMax = Integer.MIN_VALUE ;
int [] right = new int [A.length] ;
for (int i = A.length - 1 ; i > 0 ; --i) {
if (A[i -1] > A[i]) right[i - 1] = A[i -1] - A[i] + right[i];
rightMax = Math.max(rightMax, right[i - 1]);
}
return Math.max(leftMax, rightMax) ;
}
public class MaxDifference {
public static void main(String args[]) {
int array[] = { 1, 2, 1, 4, 5, 6, 7 };
// int array[] = { 3, 2, 1, 4, 5, 6, 7 };
int maxDiff = Integer.MIN_VALUE;
int mineleMent = array[0];
for (int i = 1; i < array.length; i++) {
int diff = array[i] - mineleMent;
if (diff > maxDiff) {
maxDiff = diff;
}
if (array[i] < mineleMent) {
mineleMent = array[i];
}
}
System.out.println(maxDiff);
}
/*
* Time Complexity: O(n) Auxiliary Space: O(1)
*/
}
public int maxDiff(int[] arr){
if (arr.length <= 1){
return Integer.MIN_VALUE;
}
int[] maxRight = new int[arr.length];
maxRight[arr.length - 1] = arr[arr.length-1];
for (int i = arr.length - 2; i >= 0; i--){
maxRight[i] = Math.max(arr[i], maxRight[i+1]);
}
int maxDiff = Integer.MIN_VALUE;
for (int i = 0 ; i < arr.length; i++){
maxDiff = Math.max(maxDiff , maxRight[i] - arr[i]);
}
return maxDiff;
}
public class DiffMax{
public static void main(String args[]){
int arr[] = {3,5,8,2,0,3,6,9};
int max_diff =0;
int num=arr[arr.length-1];
for(int i =arr.length-2;i>=0;i--){
if(arr[i] > num){
num = arr[i];
}else if(arr[i] <num){
max_diff = max_diff < num - arr[i]?num-arr[i]:max_diff;
}
}
System.out.println("max diff is "+max_diff);
}
}
iteration through the array actually starts at i=1,but since one may like to see the other differences between elements,I am starting from 0.
#include <iostream>
using namespace std;
void find_max(int arr [], int arr_len){
int max = arr[1] - arr[0];
for(int i = 0; i < arr_len - 1; i++ ){
//cout<< arr[i+1] - arr[i]<<" ";
if(max < arr[i+1] - arr[i]){
max = arr[i+1] - arr[i];
}
}
cout<<endl<<max<<endl;
return;
}
int main(){
int arr[] = { 0,6,14,19,20,60,61,70,85,95,100};
find_max(arr,11);
return 0;
}
Here I find the maximun and then find min before the maximun.
Then find the minnimun and then find the max after minimun.
Compare which one is greater.
void Main()
{
int[] A = new int[]{
3,4,5,7,8,9,11,12,15,4,6,7,8,100,0,99
};
Console.WriteLine(MaxDifference(A));
}
public static int MaxDifference(int[] A)
{
int max = int.MinValue;
int max_min = int.MaxValue;
int max_index = -1;
int min = int.MaxValue;
int min_max = int.MinValue;
int min_index = -1;
for(int i = 0; i < A.Length; i++)
{
int a = A[i];
if(max < a)
{
max_index = i;
max = a;
}
if(min > a)
{
min_index = i;
min = a;
}
}
// Max Diference of max
for(int i = 0; i < max_index; i++)
{
int a = A[i];
if(max_min > a)
{
max_min = a;
}
}
for(int i = min_index + 1; i < A.Length; i++)
{
int a = A[i];
if(min_max < a)
{
min_max = a;
}
}
int min_diff = (min_max - min);
int max_diff = (max - max_min);
return (max_diff > min_diff)?max_diff:min_diff;
}
public class FindDifference {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}
}
public class FindDifference {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}
}
and
public class FindDifference {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}
}
and
public class FindDifference {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}
}
public class FindDifference {
/**
* @param args
*/
public static void main(String[] args) {
int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}
}
import java.util.*;
class MaxDifference2Elem
{
static int maxDiff(int[] arr)
{
int min=0,max=0;
int[] diff=new int[arr.length-1];
for(int i=0;i<arr.length;++i)
{
//System.out.println("arr[i]: "+arr[i]+" arr[min]: "+arr[min]);
if(arr[i]<arr[min])
min=i;
if(arr[i]>arr[max])
max=i;
if(i+1<arr.length)
diff[i]=arr[i+1]-arr[i];
}
int res=0;
if(min>max)
{
int temp=min;
min=max;
max=temp;
}
//System.out.print(min+","+max);
for(int i=min;i<max;++i)
res+=diff[i];
return res;
}
public static void main(String[] st)
{
int[] elem={1,-2,6};
System.out.println("largest difference: "+maxDiff(elem));
}
}
The top rated answer is incorrect. The question does not state that the array is sorted etc. Here's the correct solution:
public static int maxDiff(int[] arr)
{
int maxElement = arr[0];
int minElementAfterMaxElement = int.MaxValue;
int maxDrop = -1;
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] > maxElement)
{
maxElement = arr[i];
minElementAfterMaxElement = int.MaxValue;
}
else
{
minElementAfterMaxElement = Math.Min(arr[i], minElementAfterMaxElement);
maxDrop = maxElement - minElementAfterMaxElement;
}
}
return maxDrop;
}
public class MaximumDifference {
public static void main(String args[]){
int[] a = { 4, 1, 20, 5, 59, 10};
int l = a.length;
int j = l - 1;
int diff = 0;
int i = j -1;
while (i>=0)
{
if (a[j] > a[i]){
if ((a[j]-a[i]) > diff){
diff = a[j] - a[i];
}
i--;
}
else{
j=i;
i--;
}
}
System.out.println(diff);
}
}
I'm not sure of an O(n) solution, but I'm pretty sure you can do this in O(nlogn) using modified merge sort.
On each merge you do in merge sort, you have a left subarray (L) and a right subarray (R).
Assume that L has a candidate difference (CDL) and R has a candidate difference (CDR). On the merge, find the min from L and the max from R to get a candidate difference between L and R (CDLR). Now, for the array that L and R merge into, we will take Max(CDL, CDR, and CDLR) to be the candidate difference for the merged array.
Recursively, the answer bubbles all the way to the top.
1. Iterate through all elements and find MIN and MAX elements of array.
Thus, result = max - min.
2. Every time, when we change MIN , we save previous value as second element.
This is also not correct for the same reason as the previous post if the maximum has a lower array index than the minimum.
Same concept as stock buying and selling given that the buy date is before the sell date and you want maximum profit.
- Anonymous January 28, 2015