"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 &lt; 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 &lt;= T &lt;= 1000
1 &lt;= N &lt;= 100000
0 &lt;= K &lt; N
0 &lt;= popularity_of_friend &lt;= 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 &lt; T; i++){
            int friendsStart = Integer.parseInt(scanner.next());
            int friendsDelete = Integer.parseInt(scanner.next());
            ArrayList&lt;Integer&gt; inputList = new ArrayList&lt;Integer&gt;();
            int currentPos = 0;
            for(int j = 0; j &lt; friendsStart ; j++){
                p.add(Integer.parseInt(scanner.next()));
                if(fD &gt; 0 &amp;&amp; currentPos &gt; 0 &amp;&amp; inputList.get(currentPos) &gt; inputList.get(currentPos-1)){
                    inputList.remove(currentPos-1);
                    friendsDelete--;
                    currentPos--;
                }else{
                    currentPos++;
                }
            }

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

            //print
            for(int j = 0; j &lt; 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.
Hint: The problem statement asks you to remove friends from the end of the list as necessary. Think carefully about this.


   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