# "Remove Friends" problem time efficiency too slow

I'm doing this problem:

After getting her PhD, Christie has become a celebrity at her university, and her Facebook profile is full of friend requests. Being the nice girl she is, Christie has accepted all the requests.

Now Kuldeep is jealous of all the attention she is getting from other guys, so he asks her to delete some of the guys from her friend list.

To avoid a 'scene', Christie decides to remove some friends from her friend list, since she knows the popularity of each of the friend she has, she uses the following algorithm to delete a friend.

Algorithm Delete(Friend):
DeleteFriend=false
for i = 1 to Friend.length-1
if (Friend[i].popularity < Friend[i+1].popularity)
delete i th friend
DeleteFriend=true
break
if(DeleteFriend == false)
delete the last friend


Input: First line contains T number of test cases. First line of each test case contains N, the number of friends Christie currently has and K ,the number of friends Christie decides to delete. Next lines contains popularity of her friends separated by space.

Output: For each test case print N-K numbers which represent popularity of Christie friend's after deleting K friends.

Constraints:

1 <= T <= 1000
1 <= N <= 100000
0 <= K < N
0 <= popularity_of_friend <= 100


NOTE: Order of friends after deleting exactly K friends should be maintained as given in input.

Sample Input

3
3 1
3 100 1
5 2
19 12 3 4 17
5 3
23 45 11 77 18


Sample Output

100 1
19 12 17
77 18


Time Limit 1 sec(s) (Time limit is for each input file.)

Memory Limit 256 MB

Source Limit 1024 KB

Initially I would read and add the numbers to the list, then follow that algorithm. I figured doing what that algorithm does except as I add it in would be much faster (which it was):

import java.util.*;

class TestClass {
public static void main(String args[] ) throws Exception {
Scanner scanner = null;
try{
scanner = new Scanner(System.in);
}catch(Exception e){
return;
}
int T = Integer.parseInt(scanner.next());

//remove as i add to list
for(int i = 0; i < T; i++){
int friendsStart = Integer.parseInt(scanner.next());
int friendsDelete = Integer.parseInt(scanner.next());
ArrayList<Integer> inputList = new ArrayList<Integer>();
int currentPos = 0;
for(int j = 0; j < friendsStart ; j++){
if(fD > 0 && currentPos > 0 && inputList.get(currentPos) > inputList.get(currentPos-1)){
inputList.remove(currentPos-1);
friendsDelete--;
currentPos--;
}else{
currentPos++;
}
}

//remove remainder required to remove
while(friendsDelete > 0 && c < inputList.size()){
if(currentPos > 0 && inputList.get(currentPos) > inputList.get(currentPos -1)){
inputList.remove(currentPos-1);
friendsDelete--;
currentPos--;
}else{
currentPos++;
}
}

//print
for(int j = 0; j < inputList.size(); j++){
System.out.print(inputList.get(j) + " ");
}
System.out.println();
}
}
}


However, when I submit, it does some bigger test cases (not sure what the cases are), but it ends up being too slow. I wanted some hints as to how I can make this faster than it already is. I don't want a direct answer.

• Some of the variable names are not verbose enough IMO Commented Aug 8, 2014 at 16:05
• @Ryan Yah, I just kind of hacked it up for the site. Let me change it up so its a bit more readable. Commented Aug 8, 2014 at 16:06
• I cannot believe that your algorithm is too slow. I think that its speed is bounded by I/O... Commented Aug 8, 2014 at 17:26
• Preallocate your list using new ArrayList<Integer>(friendsStart) to avoid copying memory every time it has to double the capacity to make room for more elements. Also, is p the old name for inputList? Commented Aug 8, 2014 at 18:58
• Please don't edit the original code as it invalidates existing answers. Commented Aug 8, 2014 at 19:38

You don't actually have to remove the remaining friends to delete. Instead, just don't print them. Change your while and for to the following code.

Spoiler tags and code blocks don't interact nicely, so the solution code is base 64 encoded.

Zm9yIChpbnQgaiA9IDAsIGptYXggPSBpbnB1dExpc3Quc2l6ZSgpIC0gZnJpZW5kc0RlbGV0ZTsgaiA8IGptYXg7IGorKykgew0KICAgICBTeXN0ZW0ub3V0LnByaW50KGlucHV0TGlzdC5nZXQoaikgKyAiICIpOw0KfQ==


I believe @EmanuelePaolini is correct in that you're likely getting TLE because of I/O. You're using Scanner, which is way too slow. Try a different input method.

You can try switching to BufferedReader. String.split() is still slow, so you can combine it with StringTokenizer. Here's a sample on ideone.

Encoded:

c3RhdGljIEJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsNCnN0YXRpYyBTdHJpbmdUb2tlbml6ZXIgc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKCIiKTsNCnN0YXRpYyBpbnQgbmV4dEludCgpIHRocm93cyBJT0V4Y2VwdGlvbiB7DQoJd2hpbGUgKCFzdC5oYXNNb3JlVG9rZW5zKCkpDQoJCXN0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihici5yZWFkTGluZSgpKTsNCglyZXR1cm4gSW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSk7DQp9

• The BufferedReader and StringTokenizer made it way faster. However, it only helped pass one more test case. Still is too slow for other test cases. Commented Aug 8, 2014 at 19:09

You've missed several variable renamings which keeps your code from compiling, and those names were truly atrocious! p, c, fD? Create more descriptive names as an opportunity to practice your touch-typing skills. :) It doesn't help that the names in the original problem description weren't much better:

• Friend (singular): Holds a list of friends (plural)
• DeleteFriend (verb phrase): Indicates that a friend was deleted during the iteration (adjective)

Anyway, your new names are better, but here are some alternatives:

• friends: List of friends
• friendCount: Number of friends in original list
• deleteCount: Number of friends left to delete

As for the algorithm, you're on the right track by deleting friends as you read them, but you can take it a step further by deleting more than one when possible. For example, when you delete the previous friend, it may allow you to delete the next previous friend as well. The benefit of this is that you're always deleting from the end of the list which minimizes the amount of memory being copied for each friend deleted.

And as I stated in my comment, preallocate the full length of the list to avoid more memory copies. The array starts with ten elements by default (last time I checked), and doubles in size every time it runs out of space. That requires ten copies to handle ten thousand friends. It's not a large number, but the amount of memory being copied adds up quick.

ArrayList<Integer> friends = new ArrayList<Integer>(friendCount);


Of course, if you alter the algorithm to always delete from the end, you can skip ArrayList altogether and use a simple array of ints and avoid the overhead of Integer objects. So how can we do that?

As long as there are friends left to delete, remove as many friends as possible from the end of the list while reading. The list should always be in the "no friends can be deleted" state: every friend is at least as popular as the next friend.

The empty list obviously starts in that state, and adding the first friend maintains it. From them on when adding the next friend, keep deleting the previous friend until we find one that is at least as popular.

while deleteCount > 0:

Once you've deleted the desired number of friends, print the processed list of friends and the remaining friends in the line (no need to parse and add them to the list first). If you run out of friends to read before then, remove the last deleteCount friends in the list.