LogoKode$word
LeetCode 1365: How Many Numbers Are Smaller Than the Current Number | Java Solution, Intuition, Dry Run & Complexity Analysis
LeetCode 1365: How Many Numbers Are Smaller Than the Current Number | Java Solution, Intuition, Dry Run & Complexity Analysis

LeetCode 1365: How Many Numbers Are Smaller Than the Current Number | Java Solution, Intuition, Dry Run & Complexity Analysis

Understand LeetCode 1365 using Java with clear intuition, code explanation, dry run, and complexity discussion.

15 views
0
0
LeetCodeEasyTwo PointerArrayJava
Github icon
Github icon
Listen to articleAudio version

Introduction

In this problem, we are given an integer array nums.

For every element in the array, we must calculate how many numbers are smaller than the current number.

The result should be stored in another array where:

  1. Each index contains the count of smaller numbers
  2. Comparison must be done against every other element
  3. We cannot count the element itself

This is a beginner-friendly array problem that teaches comparison logic and nested loop thinking.

Problem Statement

Given the array nums, return an array answer such that:

answer[i] = count of numbers smaller than nums[i]

Question Link

Problem Link -: Leetcode 1365

Example

Input

nums = [8,1,2,2,3]

Output

[4,0,1,1,3]

Explanation

  1. 8 → four smaller numbers → 1,2,2,3
  2. 1 → no smaller number
  3. 2 → one smaller number → 1
  4. 2 → one smaller number → 1
  5. 3 → three smaller numbers → 1,2,2

Understanding the Problem

We need to check:

For every element:

How many values in the array are smaller than it?

This means:

  1. Compare one number with all other numbers
  2. Count valid smaller values
  3. Store count in answer array

Intuition

The simplest idea is:

  1. Pick one number
  2. Compare it with every element
  3. Count smaller numbers
  4. Save result
  5. Repeat for all indices

Since constraints are small:

nums.length <= 500

Brute force works perfectly.

Approach

We use two loops:

  1. Outer loop → selects current number
  2. Inner loop → compares with all numbers

If:

nums[j] < nums[i]

Then increase count.

Java Solution

class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int i = 0;
int j = 1;
int ans[] = new int[nums.length];
int cou = 0;

while(i < nums.length){

if(i != j && nums[i] > nums[j]){
cou++;
}

j++;

if(j == nums.length){
ans[i] = cou;
i++;
cou = 0;
j = 0;
}
}

return ans;
}
}

Code Explanation

Variables

i

Current element index.

j

Used for comparison.

cou

Stores count of smaller numbers.

ans[]

Final result array.

Step-by-Step Logic

Step 1

Pick current number using:

i

Step 2

Compare with every number using:

j

Step 3

If another value is smaller:

nums[i] > nums[j]

Increase count.

Step 4

Store count.

Step 5

Move to next element.

Dry Run

Input

nums = [8,1,2,2,3]

First Element = 8

Compare with:

NumberSmaller?
1Yes
2Yes
2Yes
3Yes

Count = 4

ans[0] = 4

Second Element = 1

No smaller number.

ans[1] = 0

Third Element = 2

Smaller number:

1

Count = 1

ans[2] = 1

Final Answer

[4,0,1,1,3]

Time Complexity

We compare every element with every other element.

Complexity

O(N²)

Because:

  1. Outer loop = N
  2. Inner loop = N

Total:

N × N

Space Complexity

We only store output array.

Complexity

O(N)

Better Clean Version (Recommended)

Your logic works, but interviewers usually prefer readable code.

class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {

int n = nums.length;
int[] ans = new int[n];

for(int i = 0; i < n; i++) {

int count = 0;

for(int j = 0; j < n; j++) {

if(i != j && nums[j] < nums[i]) {
count++;
}
}

ans[i] = count;
}

return ans;
}
}

Optimized Approach

Since:

0 <= nums[i] <= 100

We can use frequency counting.

This gives:

O(N + K)

Where:

  1. N = array size
  2. K = range of values

Common Mistakes

1. Comparing Same Index

Wrong:

nums[i] > nums[i]

Correct:

i != j

2. Forgetting Reset Count

Wrong:

count keeps increasing

Correct:

count = 0

after each iteration.

3. Index Out Of Bounds

Always ensure:

j < nums.length

Interview Tips

This problem teaches:

  1. Nested loops
  2. Array traversal
  3. Counting logic
  4. Comparison problems
  5. Brute force thinking

Interviewers may ask:

Can you optimize it?

Answer:

Use counting sort or prefix frequency.

FAQs

Is this problem easy?

Yes. It is beginner-friendly.

Is brute force accepted?

Yes.

Constraints are small.

Can we optimize?

Yes.

Using counting frequency array.

Is this asked in interviews?

Yes.

Especially for beginners.

Final Thoughts

LeetCode 1365 is a simple array problem that helps build strong fundamentals.

You learn:

  1. How comparisons work
  2. How nested loops solve counting problems
  3. How to convert logic into output arrays


Related Articles

Sort Colors

Sort Colors

LeetCode question 75 Medium

Read Article
Max Consecutive Ones III – Sliding Window with Limited Flips

Max Consecutive Ones III – Sliding Window with Limited Flips

Learn how to maximize consecutive 1's in a binary array by flipping at most K zeros using an optimized sliding window approach.

Read Article
LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

Master the Monotonic Stack Pattern With HashMap Optimization — Step-by-Step Dry Run, Brute Force to O(n) Solution, and Full Complexity Analysis in Java

Read Article
Longest Subarray of 1's After Deleting One Element – Sliding Window Approach

Longest Subarray of 1's After Deleting One Element – Sliding Window Approach

Learn how to maximize consecutive 1's in a binary array by deleting exactly one element using an efficient sliding window technique.

Read Article
Ai Assistant Kas