What is the time complexity of Online Election?

The optimal solution has a time complexity of O(log n).

What data structures are used to solve Online Election?

This problem uses Array, Hash Table, Binary Search, Design. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Online Election?

Insight 1: Pre-computation of the leaders at each time point is crucial for efficient querying. Instead of re-calculating the leader for every query, we calculate it once during initialization. Insight 2: Binary search is the correct approach for efficiently finding the correct time index in the `times` array for a given query time `t`. Because the `times` array is strictly increasing, it is perfect for binary search.

Which companies ask LeetCode 911. Online Election in interviews?

This problem is frequently asked at Atlassian, CARS24.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Online Election - LeetCode 911 Solution

Online Election - Complete Solution Guide

Online Election is LeetCode problem 911, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given two integer arrays persons and times . In an election, the i th vote was cast for persons[i] at time times[i] . For each query at a time t , find the person that was leading the election at time t . Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins. Implement the TopVotedCandidate class: TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays. int q(int t) Returns

Detailed Explanation

The problem simulates an online election where votes are cast at specific times. We are given two arrays, `persons` and `times`, representing the person voted for and the time the vote was cast, respectively. The goal is to implement a `TopVotedCandidate` class that allows us to query who was leading the election at any given time `t`. The votes cast at time `t` *are* counted for the query. In case of a tie, the most recent vote (among the tied candidates) wins. The class has two methods: a constructor `TopVotedCandidate(persons, times)` to initialize with the vote data, and a query method `q(t)` that returns the leading candidate at time `t`.

Solution Approach

The solution pre-computes the leader at each time a vote is cast. During initialization, we iterate through the `persons` and `times` arrays, keeping track of the vote count for each person. As we iterate, we determine the current leader and append it to the `leaders` array. When a query `q(t)` is made, we use binary search on the `times` array to find the correct time index corresponding to time `t`. Because we need the vote at time `t` to be counted, we perform a 'right' binary search to find the rightmost time `t`. Once we have that index, we decrement it by 1 to find the appropriate leader in our `leaders` array.

Step-by-Step Algorithm

Step 1: **Initialization (`__init__`)**: Create arrays to store `times` and `leaders`.
Step 2: **Initialization**: Create a dictionary/map `counts` to store vote counts for each person.
Step 3: **Initialization**: Initialize `leader` to -1 and `max_votes` to 0.
Step 4: **Initialization**: Iterate through the `persons` array. For each `person`, increment their count in the `counts` dictionary.
Step 5: **Initialization**: If the current `person`'s vote count is greater than or equal to `max_votes`, update `max_votes` and set the current `person` as the `leader`.
Step 6: **Initialization**: Append the current `leader` to the `leaders` array after each vote is processed.
Step 7: **Query (`q(t)`)**: Use binary search (`bisect_right` in Python, `upper_bound` in C++, custom `binarySearchRight` in Java, equivalent implementation in C) on the `times` array to find the index of the first time strictly *greater* than `t`.
Step 8: **Query**: Return the element at index `idx - 1` from the `leaders` array. This is the leader at time `t`.

Key Insights

Insight 1: Pre-computation of the leaders at each time point is crucial for efficient querying. Instead of re-calculating the leader for every query, we calculate it once during initialization.
Insight 2: Binary search is the correct approach for efficiently finding the correct time index in the `times` array for a given query time `t`. Because the `times` array is strictly increasing, it is perfect for binary search.
Insight 3: The problem emphasizes that a vote at time `t` is included in the query. This means we need to use `bisect_right` or its equivalent to find the index of the first time strictly *greater* than `t`, and then decrement that index to get the correct time point to determine the leader.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Binary Search, Design.

Companies

Asked at: Atlassian, CARS24.

Online Election | LeetCode 911

Medium

Array Hash Table Binary Search Design

Time: O(log n)Space: O(n)

Solution Code

Available in:

import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

class TopVotedCandidate {

    private int[] times;
    private List<Integer> leaders;

    public TopVotedCandidate(int[] persons, int[] times) {
        this.times = times;
        this.leaders = new ArrayList<>();

        Map<Integer, Integer> counts = new HashMap<>();
        int leader = -1;
        int max_votes = 0;

        for (int person : persons) {
            counts.put(person, counts.getOrDefault(person, 0) + 1);
            if (counts.get(person) >= max_votes) {
                max_votes = counts.get(person);
                leader = person;
            }
            this.leaders.add(leader);
        }
    }

    public int q(int t) {
        int idx = binarySearchRight(this.times, t);
        return this.leaders.get(idx - 1);
    }

    private int binarySearchRight(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj.q(t);
 */

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 911: Online Election - Detailed explanation and solution approaches.

Topics

Array Hash Table Binary Search Design

Companies

AtlassianCARS24

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:911

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: **Initialization (`__init__`)**: Create arrays to store `times` and `leaders`.
2
Step 2: **Initialization**: Create a dictionary/map `counts` to store vote counts for each person.
3
Step 3: **Initialization**: Initialize `leader` to -1 and `max_votes` to 0.
4
Step 4: **Initialization**: Iterate through the `persons` array. For each `person`, increment their count in the `counts` dictionary.
5
Step 5: **Initialization**: If the current `person`'s vote count is greater than or equal to `max_votes`, update `max_votes` and set the current `person` as the `leader`.
6
Step 6: **Initialization**: Append the current `leader` to the `leaders` array after each vote is processed.
7
Step 7: **Query (`q(t)`)**: Use binary search (`bisect_right` in Python, `upper_bound` in C++, custom `binarySearchRight` in Java, equivalent implementation in C) on the `times` array to find the index of the first time strictly *greater* than `t`.
8
Step 8: **Query**: Return the element at index `idx - 1` from the `leaders` array. This is the leader at time `t`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The initialization process iterates through the input arrays of length n once, resulting in O(n) time complexity. The binary search in the `q(t)` method takes O(log n) time, as it halves the search space in each step. We store the `times` and `leaders` arrays, both of size n, resulting in O(n) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Linear Search

Instead of binary search, a linear search could be used to find the correct time index. Iterate through the `times` array until we find a time greater than `t`.

Time: O(n) for the query method, O(n) for initialization.Space: O(n)

Trade-offs: The linear search approach is simpler to implement but less efficient, especially when many queries are performed. It is only appropriate if the number of queries is small.

✨

Key Insights

1Insight 1: Pre-computation of the leaders at each time point is crucial for efficient querying. Instead of re-calculating the leader for every query, we calculate it once during initialization.
2Insight 2: Binary search is the correct approach for efficiently finding the correct time index in the `times` array for a given query time `t`. Because the `times` array is strictly increasing, it is perfect for binary search.
3Insight 3: The problem emphasizes that a vote at time `t` is included in the query. This means we need to use `bisect_right` or its equivalent to find the index of the first time strictly *greater* than `t`, and then decrement that index to get the correct time point to determine the leader.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: Query time `t` is earlier than the first vote. The bisect_right returns 0 so the code correctly returns leaders[0-1] which becomes leaders[-1]. In Python lists support negative indexing, whereas in languages like Java/C/C++, this needs to be handled with some extra checks or making sure the query time is within the bounds of times.
Edge case 2: Query time `t` is exactly a time when a vote was cast. bisect_right will return the index one greater than the index for that time. Since we want the leader *at* that time, we decrement that index before looking up the leader.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using `bisect_left` (or its equivalent) instead of `bisect_right`. This would result in returning the leader at the time *before* `t` if `t` is exactly equal to one of the times in the `times` array. It would also be wrong if `t` occurs between two times in `times`.

✗Common mistake 2: Not handling the edge case where `t` is smaller than all times. In Python, negative indexing might hide the error, but in other languages, accessing `leaders[-1]` will cause an out-of-bounds error.

✗Common mistake 3: Re-computing the leading candidate for every query. This would lead to a time complexity of O(n) for each query, making the overall solution inefficient.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing stock prices over time. You might want to know the highest stock price at any given point in time.

🏦Real-world scenario 2: Determining the popularity of a product feature over time based on user feedback data. Similar to an election, feature requests accumulate over time and you can use a similar approach to track the most popular feature at any given moment.

🎮Real-world scenario 3: Tracking server load and identifying the peak load time within a defined window. You can pre-compute the load at different times and quickly query the peak load for any given time using binary search.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 12, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Online Election"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?