forked from RyanFehr/HackerRank
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.java
More file actions
53 lines (43 loc) · 2 KB
/
Solution.java
File metadata and controls
53 lines (43 loc) · 2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//Problem: https://www.hackerrank.com/challenges/minimum-loss
//Java 8
/*
Initial Thoughts: We can sort the array to reduce the number of comparisons since
we know that the absolute difference is always smallest between
adjacent elements in a sorted array. Then because we have the
stipulation that we must buy the house before we can sell it
we should verify that the buy price we are using is a price
that occurred in a year prior to the sell price year. We can
accomplish this by using a map that will be at most size n and
will store distinct key,value pairs where the key is the price
and the value is the year.
Time Complexity: O(n log(n)) //We must sort the input array
Space Complexity: O(n) //We use a map to store the price,year pairs
*/
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner input = new Scanner(System.in);
int n = input.nextInt();
long[] prices = new long[n];
HashMap<Long,Integer> indices = new HashMap<>();
//Populate prices array with the input
for(int i = 0; i < n; i++){
prices[i] = input.nextLong();
indices.put(prices[i],i);
}
Arrays.sort(prices);//Performs a double pivot quicksort and sorts ascending
Long minimumLoss = Long.MAX_VALUE;
//Iterate from end to start
for(int i = n-1; i >0; i--){
//Make sure it is a smaller loss
if(prices[i]-prices[i-1] < minimumLoss){
//Verify if the pair is a valid transaction
if(indices.get(prices[i]) < indices.get(prices[i-1]))
minimumLoss = prices[i]-prices[i-1];
}
}
System.out.println(minimumLoss);
}
}