Implement a Cursor-Based Text Editor
HarveySoftware Engineer · OnsiteLast updated
Design an in-memory cursor-based text editor supporting character insertion, deletion, and cursor navigation with efficient time complexity.
Problem Statement
Design a text editor that maintains a text string and a cursor position. The editor starts empty with the cursor at position 0 (the very beginning of the document).
Implement the TextEditor class:
TextEditor(): Initializes the text editor with an empty text.insert(text: str) -> None: Insertstextat the current cursor position. The cursor moves to the right of the newly inserted characters.delete(k: int) -> int: Deletes up tokcharacters immediately to the left of the cursor. The cursor shifts left by the number of deleted characters. Returns the actual number of characters deleted.cursor_left(k: int) -> str: Moves the cursorkpositions to the left (stopping at index0if it reaches the start of the text). Returns the lastmin(10, len)characters immediately to the left of the cursor (wherelenis the number of characters to the left of the cursor).cursor_right(k: int) -> str: Moves the cursorkpositions to the right (stopping at the end of the text if it reaches the end). Returns the lastmin(10, len)characters immediately to the left of the cursor.
Example
editor = TextEditor()
editor.insert("hello") # Text: "hello|", cursor is after 'o'
editor.delete(2) # Deletes 'l' and 'o', returns 2. Text: "hel|"
editor.insert("p") # Text: "help|"
editor.cursor_left(2) # Moves cursor 2 left: "he|lp", returns "he"
editor.cursor_right(1) # Moves cursor 1 right: "hel|p", returns "hel"
editor.delete(10) # Attempts to delete 10 left of cursor, deletes 3 ('h', 'e', 'l'), returns 3. Text: "|p"
Constraints
1 <= len(text) <= 40perinsertcall1 <= k <= 40perdelete,cursor_left, andcursor_rightcalltextconsists only of lowercase English letters.- At most
2 * 10^5calls will be made in total across all methods. - Operations must run efficiently enough to handle heavy sequences of insertions, moves, and deletions without quadratic time degradation.
Hints
Hint 1
Notice that the cursor naturally splits the document into two halves: text before the cursor and text after the cursor.
Hint 2
Using a single dynamic array or string requires O(n) shifts for each insertion or deletion in the middle of the text.
Hint 3
Consider maintaining two separate stacks or deques (one for characters to the left of the cursor and one for characters to the right) to make cursor moves and edits O(1) per character.
Follow-up questions
- How would you support an Undo and Redo mechanism without snapshotting the entire state on every keystroke?
- If the document grows to gigabytes in size and requires random-access jumps (e.g., jump to line 50,000), how would you replace the two-stack approach with data structures like a Rope or Piece Table?
- How would you adapt this data model to support collaborative editing where multiple cursors concurrently edit the document?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.