Created
February 6, 2016 18:39
-
-
Save pjoshi30/25a425fd879e4bb9e22a to your computer and use it in GitHub Desktop.
Quora upvotes challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.io.*; | |
import java.util.ArrayList; | |
import java.util.List; | |
public class Solution { | |
public static void main(String args[] ) throws Exception { | |
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
String line = br.readLine(); | |
String[] nk = line.split("\\s+"); | |
int n = 0; | |
int k = 0; | |
if(nk.length > 1){ | |
n = Integer.parseInt(nk[0].trim()); | |
k = Integer.parseInt(nk[1].trim()); | |
} else { | |
System.exit(0); | |
} | |
String arrStr = br.readLine(); | |
String[] arrInts = arrStr.split("\\s+"); | |
List<Integer> arr = new ArrayList<>(); | |
for(String arrInt: arrInts){ | |
arr.add(Integer.parseInt(arrInt.trim())); | |
} | |
//arr is the list of integers. n and k are the size of the array and window respectively. | |
StringBuilder sb = new StringBuilder(); | |
for(int i = 0; i < n-k+1; i++){ | |
sb.append(String.valueOf(findDiffInSubrange(arr, i, k))); | |
sb.append("\n"); | |
} | |
try(BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out))) { | |
log.write(sb.toString()); | |
log.flush(); | |
} | |
catch (Exception e) { | |
e.printStackTrace(); | |
} | |
//The above is a worst case runtime of O((n-k)*k). Can we do better? | |
} | |
private static long findDiffInSubrange(List<Integer> a, int start, int k){ | |
int i = start; | |
int end = start + k - 1; | |
long cndec = 1; | |
long cninc = 1; | |
long ninc = 0; | |
long ndec = 0; | |
while(i < end){ | |
while(i < end && a.get(i) == a.get(i+1)){ | |
cndec++; | |
cninc++; | |
i++; | |
} | |
while(i < end && a.get(i) <= a.get(i+1)){ | |
cndec++; | |
if(a.get(i) == a.get(i+1)){ | |
cninc++; | |
} | |
i++; | |
} | |
while(i < end && a.get(i) >= a.get(i+1)){ | |
cninc++; | |
if(a.get(i) == a.get(i+1)){ | |
cndec++; | |
} | |
i++; | |
} | |
ndec += calculateSubrange(cndec); | |
ninc += calculateSubrange(cninc); | |
cndec = 1; | |
cninc = 1; | |
} | |
return (ndec - ninc); | |
} | |
private static long calculateSubrange(long k){ | |
return (k * (k-1)) >>> 1; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment