r/learnjava • • Apr 17 '24

Implementing efficient Stack data structure in Java

Having already solved the Keystrokes problem on Open Kattis using Python3, I'm now trying to re-implement the same algorithm in Java. I've come up with below class which compiles and runs fine but runs into the time-out error when I submit for evaluation. What can I do to make it more efficient?

import java.util.*;

class lyklagangriti {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		Stack<Character> l = new Stack<>();
		Stack<Character> r = new Stack<>();
		for(int i=0;i<s.length();i++) {
			char c = s.charAt(i);
			char item;
			switch(c) {
				case 'L':
					item = l.pop();
					r.push(item);
					break;
				case 'R':
					item =r.pop();
					l.push(item);
					break;
				case 'B':
					l.pop();
					break;
				default:
					l.push(c);
			}
		}
		for(char c : l) {
			System.out.print(c);
		}
		while(r.size() > 0) {
			char c = r.pop();
			System.out.print(c);
		}
		System.out.println("");
	}
}

Edit

Special thanks to /u/Cengo789 for suggesting ArrayDeque instead of Stack, and to /u/-doublex- for suggesting BufferedReader instead of Scanner for reading the input. After implementing these ideas, the program passes the test in only 0.21 seconds!

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class lyklagangriti {
	
	public static void main(String[] args) throws IOException {
		//Scanner sc = new Scanner(System.in);
		BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
		String s = bi.readLine();

		//String s = sc.nextLine();
		Deque<Character> l = new ArrayDeque<Character>();
		Deque<Character> r = new ArrayDeque<Character>();
		for(int i=0;i<s.length();i++) {
			char c = s.charAt(i);
			char item;
			switch(c) {
				case 'L':
					item = l.pollLast();
					r.addFirst(item);
					break;
				case 'R':
					item =r.pollFirst();
					l.addLast(item);
					break;
				case 'B':
					l.pollLast();
					break;
				default:
					l.addLast(c);
			}
		}
		StringBuilder sb  = new StringBuilder(l.size() + r.size());
		for(char c : l) {
			sb.append(c);
		}
		for(char c : r) {
			sb.append(c);
		}
		System.out.println(sb);
	}
}
0 Upvotes

12 comments sorted by

•

u/AutoModerator Apr 17 '24

Please ensure that:

  • Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions

  • You include any and all error messages in full - best also formatted as code block

  • You ask clear questions

  • You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit/markdown editor: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

2

u/Cengo789 Apr 17 '24

Try using ArrayDeque instead of Stack. The Stack class is built on top of the very old Vector class and it’s synchronized. So you are probably paying for something you don’t need.

1

u/pyeri Apr 17 '24

I did try the ArrayDeque implementation but still the same result:

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class lyklagangriti {
	
	public static void main(String[] args) throws IOException {
		//Scanner sc = new Scanner(System.in);
		BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
		String s = bi.readLine();

		//String s = sc.nextLine();
		Deque<Character> l = new ArrayDeque<Character>();
		Deque<Character> r = new ArrayDeque<Character>();
		for(int i=0;i<s.length();i++) {
			char c = s.charAt(i);
			char item;
			switch(c) {
				case 'L':
					item = l.pollLast();
					r.addFirst(item);
					break;
				case 'R':
					item =r.pollFirst();
					l.addLast(item);
					break;
				case 'B':
					l.pollLast();
					break;
				default:
					l.addLast(c);
			}
		}
		for(char c : l) {
			System.out.print(c);
		}
		for(char c : r) {
			System.out.print(c);
		}
		System.out.println("");
	}
}

2

u/Cengo789 Apr 17 '24 edited Apr 17 '24

The problem seems to come from the repeated calls to System.out.print. Replace these with the following:

StringBuilder sb = new StringBuilder(l.size() + r.size());
        
l.forEach(sb::append);
r.forEach(sb::append);

System.out.println(sb);

And your code passes in 0.25s

1

u/pyeri Apr 18 '24

Thanks a ton! The System.out.print was indeed the issue here.

1

u/-doublex- Apr 17 '24

Is it normal that the input comes from stdin?

1

u/pyeri Apr 17 '24

Yep. that's how it works with other languages and even with Java with earlier problems I've solved.

The issue here is of performances for test cases with larger input.

1

u/-doublex- Apr 17 '24

Ah ok so you confirm you get points for small inputs. You should still pay attention to this comment in their knowledge base:

Scanner sc = new Scanner(System.in); /* Note that scanner can be very slow on large inputs. Consider using a buffered reader such as the KattIO library if the problem has large inputs*/

Just to make sure it has nothing to do with reading the input.

1

u/pyeri Apr 17 '24

Thanks for bringing that to notice! I will look into this.

Small inputs work fine on my local machine.

1

u/-doublex- Apr 17 '24

Yeah, your code seems to run in O(n) so I can't see any issues there. Maybe just too much memory used by keeping two stacks.

1

u/pyeri Apr 17 '24

I tried with BufferedReader instead of Scanner with the same results:

	BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
	String s = bi.readLine();

1

u/Housy5 Apr 17 '24

How about forgetting all them stacks and just use a int as a cursor and StringBuffer to insert and delete chars in what ever index the cursor is current is at and increment or decrement the cursor when you need to go left or right.