Questions tagged [complexity]
Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.
419 questions
5
votes
1
answer
305
views
Iterative DFS with Optimized Space Complexity
Background
I can't seem to find an existing answer solving this doubt of mine.
In academic books, it seems that DFS is usually presented in both recursive and iterative forms.
The implementations ...
- 151
7
votes
3
answers
1k
views
Naive attempt at implementing a dictionary in C. Stack-based and O(n)
I am a C++ programmer trying to learn C.
Please critique my C code here. I am trying to make a small "hash table" that's \$O(n)\$ lookup. But, it is stack-based and so should be no slower ...
- 397
5
votes
4
answers
477
views
Count number of substrings in less time
Given an input string contains letters from 'a' to 'g'
Count how many substrings are there in the input string such that
frequency of any character inside the substring is not more than the
number of ...
- 373
13
votes
5
answers
2k
views
solve n*m matrix processing in less time
I want to solve a problem in less time complexity. Here are the details:
Given an n*m matrix, n rows and m columns. Initially, the matrix is empty filled with 0s.
...
- 373
6
votes
4
answers
481
views
Traversal Heap Sort (No Extractions)
I developed a heap sort variant that sorts a heap through traversal. Unlike in the standard heap sort, the algorithm does not remove the min element from the heap instead it traverses all the nodes of ...
1
vote
2
answers
387
views
Median of two sorted arrays in Python
Problem Statement
(Source: Leetcode Problem 4: Median of Two Sorted Arrays [Hard])(Topics: [Array] [Binary Search] [Divide and Conquer])
Given two sorted arrays ...
- 499
2
votes
2
answers
202
views
How to optimize and refactor C# method for validating business rules in terms of readability, maintainability, and performance?
I'm working on a C# project and have a bloater method ValidateBusinessRules that checks a series of business rules for validating the operations. The current code ...
- 141
2
votes
2
answers
69
views
LFU cache in Kotlin
I've been working on the classic LFU (Least Frequently Used) cache running in O(1) time problem lately and, as a student, I kind of struggled with the algorithms I found online. I got most of the idea ...
- 23
5
votes
1
answer
371
views
Fast and precise summation of random numbers
I'm trying to first formulate this challenge.
In short, we want to sum up an stream of random numbers with the following objective:
The objective is "simply" to sum up as many sequences as ...
- 244
2
votes
1
answer
211
views
Hackerrank "New Year chaos" solution - permute sequence by swapping adjacent terms
I was doing the Hackerrank "New Year chaos" problem. Here is the description:
It is New Year's Day and people are in line for the Wonderland
rollercoaster ride. Each person wears a sticker ...
- 49
5
votes
2
answers
808
views
Simplify complexity [closed]
I came across this question which asks to create a function which will return true/false based on the passed array containing all the letters to make up the passed word. Each letter from array can ...
- 51
7
votes
1
answer
257
views
Colorful Subgraph Dynamic Programming Solution and a Naive One
Given a graph \$G(V, E)\$ with vertices \$V\$ and edges \$E\$, where each vertex is associated with a single color from a set of colors \$C=\{1, 2, ..., k\}\$, we define the following problem:
Problem ...
4
votes
1
answer
153
views
Longest spell to cast from pages of spellbook follow-up
This question is from the PCTC 2022 R2 Past Paper and is a follow-up on my previous question. Previous question
I have implemented several solutions suggested, such as creating an array with pages ...
- 109
6
votes
4
answers
596
views
Longest spell to cast from pages of spellbook
While practicing for a school coding challenge, I came across this problem. My code got the right answers but exceeded the time limited. Any tips for how to reduce the time complexity?
https://pctc....
- 109
4
votes
3
answers
631
views
Leetcode 3sum problem solution
The problem is:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where ...
- 41