How to write algorithm analysis

https://leetcode.com/contribute/

Write for LeetCode and get paid!

Help us build a comprehensive collection of easily-understandable editorial solutions. You don’t have to be an experienced writer. If you have the technical chops and a knack of explaining things, we are here to help you to get published. Start writing now and get rewarded, get published on our site with over 10 million unique page views each month, and make up to $200 per article.


What we look for in articles:

  1. Thought process. What leads you into thinking this way?
  2. Easy to understand and accessible to beginners.
  3. Clear and concise explanation.

How to write:

    1. In the problem list page, choose a problem that does not have an editorial solution. The problem does not have an editorial if it does not have the file icon () besides its title.
    2. Click on the problem title to navigate to the problem description page. Click on the “Solution” tab and notice there is a green “Write for LeetCode” button. We will revisit this later.
    3. Now you can start writing by creating a new Markdown document. We strongly recommend to download a good Markdown editor such as Atom (available both on Windows and Mac) to edit your article. Once in Atom, you may enable live Markdown preview by navigating to the menu bar and click on “Packages” -> “Markdown Preview” -> “Toggle Preview”, or in Mac the shortcut is `CTRL + SHIFT + M`. Below is a snapshot of how Atom editor looks like:
    4. Copy this simple template to your Markdown editor to get started:
#### Approach #1 Brute Force [Time Limit Exceeded]

**Intuition**

Check all the substring one by one to see if it has no duplicate character.

**Algorithm**

Suppose we have a function `boolean allUnique(String substring)` ....

**Java**

```java
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }
}
```

**Complexity Analysis**

* Time complexity : $$O(n^3)$$.

To verify if characters within index range $$[i, j)$$ are all unique, we need to scan all of them. Thus, it costs $$O(j - i)$$ time.

For a given `i`, the sum of time costed by each $$j \in [i+1, n]$$ is

$$
\sum_{i+1}^{n}O(j - i)
$$

Thus, the sum of all the time consumption is:

$$
O\left(\sum_{i = 0}^{n - 1}\left(\sum_{j = i + 1}^{n}(j - i)\right)\right) =
O\left(\sum_{i = 0}^{n - 1}\frac{(1 + n - i)(n - i)}{2}\right) =
O(n^3)
$$

* Space complexity : $$O(min(n, m))$$. We need $$O(k)$$ space for checking a substring has no duplicate characters, where $$k$$ is the size of the `Set`. The size of the Set is upper bounded by the size of the string $$n$$ and the size of the charset/alphabet $$m$$.

---
#### Approach #2 Sliding Window [Accepted]

**Algorithm**

The naive approach ...

**Java**

```java
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
        }
    }
}
```

**Complexity Analysis**

* Time complexity : $$O(2n) = O(n)$$. In the worst case each character will be visited twice by $$i$$ and $$j$$.

* Space complexity : $$O(min(m, n))$$. Same as the previous approach. We need $$O(k)$$ space for the sliding window, where $$k$$ is the size of the `Set`. The size of the Set is upper bounded by the size of the string $$n$$ and the size of the charset/alphabet $$m$$.

Don’t worry about the $$<math block>$$ signs, those are latex block for rendering math equation. We do support LaTex to format math equation, if you are not familiar with that I suggest you learn it as you go.

  1. Edit your article as necessary. You should show all possible solutions. For example, a problem may start with a sub-optimal approach – Approach #1 (Brute force) [Time Limit Exceeded], to a more optimal solution – Approach #2 (Binary Search) [Accepted], then finally to the best optimal solution Approach #3 (Two Pointers) [Accepted]. Each solution should start with an Intuition section to give a general idea of the intuition behind the approach, and must be accompanied by its own Complexity analysis section.
  2. After you are finished, submit by publishing your markdown document to Discuss! Remember from Step 2. where you found the “Write for LeetCode” button? Click on the button and you will be redirected to the relevant Discuss topic.
  3. Click on “New Topic” and enter a topic title. The topic title must follow this format:
    Solution by <username>

    where <username> is your LeetCode username, not your Discuss username. Paste your markdown document in the compose area, then click “Submit”.

 


Frequently Asked Questions

Are there some writing samples I can look at?

Sure. Here’s some examples:

  1. Number of Digit One
  2. Trapping Rain Water

Can I add figures or animations into the article?

Yes sure! If a picture is worth a thousand words, why not? We strongly encourage authors to add pictures or even animations to help illustrate an idea. For animation, you can upload a .gif with your markdown document. We will have someone to help you convert the .gif animation to our diaporama format when we decide to publish your article as editorial solution. See here for an example of how the diaporama looks like.

What is the difference between an editorial solution and solutions posted by the community in Discuss?

In general, editorial solution has more in-depth explanation (besides code) compared to solutions posted in Discuss.

How many number of words should I write per article?

We do not enforce on the number of words each author should write. We recommend to write the article in a concise manner and not more than 200 words.

What is the process you use to determine the best article to publish?

We will look at all the top articles that are voted by the community and choose one we like the most. Once an article is chosen, we will contact its author and work together to publish it.

How does the reward process looks like?

The payment for each published editorial ranges from $100-$200 USD. The price will be based on the complexity of the problem or article. Once we contact you to publish, you will receive an upfront payment of $50. Upon successful completion in publishing the editorial, you will receive the rest of payment.

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s