12/20/2025
ASSIGNMENT
Name – Rishank Gupta
Course – [Link] CSE
Year - 3rd Year
Collage – Galgotias University
Index
[Link] Problem Statement
Part A–
1 Largest Rectangle in Histogram(Leetcode – 84)
2 Decode String (Leetcode – 394)
Part B–
1 Asteroid Collision (Leetcode – 735)
Part A
Largest Rectangle in Histogramef
Given an array of integers heights representing the histogram's bar height where the
width of each bar is 1, return the area of the largest rectangle in the [Link]
the largest rectangular area possible within a histogram, represented by an array of
integer bar heights, where each bar is assumed to have a width of 1.
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1. The largest
rectangle is shown in the red area, which has an area = 10 units.
Intuition
For this question we are going to implement the Stack data structure where for each
element you have to find the previous smaller element and next smaller element
when we find this then we can simply calculate area for each block with the formula
area=arr[i]*(nse[i]*pse[i]-1)
and a variable max in which we compare and find max area
.
Code-
Decode String
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the
square brackets is being repeated exactly k times. Note that k is guaranteed to
be a positive integer.
You may assume that the input string is always valid; there are no extra white
spaces, square brackets are well-formed, etc. Furthermore, you may assume that
the original data does not contain any digits and that digits are only for those
repeat numbers, k. For example, there will not be input like 3a or 2[4].
Example 1:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Code-
Part B
Asteroid Collision
We are given an array of asteroids of integers representing asteroids in a row.
The indices of the asteroid in the array represent their relative position in space.
For each asteroid, the absolute value represents its size, and the sign represents
its direction (positive meaning right, negative meaning left). Each asteroid
moves at the same speed.
Example 1:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5
collide resulting in -5. The 10 and
-5 collide resulting in 10.
Intuition
Stack stores asteroids that are moving right.
Jab koi left-moving asteroid aata hai, woh stack ke top se fight karta hai jab
tak:
1. ya toh current destroy ho jaaye
2. ya stack ka asteroid destroy ho jaaye
3. ya dono equal ho ke khatam ho jaayein.
Code-
Time & Space Complexity
Time Complexity - O(n)
Space Complexity - O(n)