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
363
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
558
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 ...
- 367
12
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.
...
- 367
7
votes
4
answers
552
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 ...
2
votes
2
answers
437
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 ...
- 619
2
votes
2
answers
271
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
94
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
396
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
276
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
857
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
307
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
169
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
630
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
728
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
3
votes
1
answer
155
views
Handwriting progressive drawing
Implementation to progressively draw symbols, when provided with symbol implementations it supports any type of symbols, though for the review purpose just two hand written latin symbols are supported ...
user279411
-2
votes
2
answers
121
views
complexity reduction (refacto) [closed]
I'm trying to reduce the complexity of this piece of code following a SonarQube error. I have several similar blocks, and even if I try to extract them into private methods, the Sonar error persists.
...
- 11
3
votes
2
answers
601
views
One Piece Treasure- Find the number of palindromic substrings in a large substring
I'm trying to solve the below question:
A string of characters X (all in lowercase) of length n is present. We can ask a query <...
- 222
1
vote
1
answer
144
views
3
votes
2
answers
142
views
Quickselect algorithm implementation and its time-complexity
I wrote this code to find kth smallest element in the array by renowned algorithm quickselect. Here is the link where you can see the working code.
What points are there to be improved? Could you ...
1
vote
1
answer
405
views
Finding highly correlated variables in a dataframe by evaluating its correlation matrix's values
I read data from Excel into a Pandas DataFrame, so that every column represents a different variable, and every row represents a different sample. I made the function below to identify potential ...
- 25
2
votes
2
answers
131
views
For two sequences N and M, display counts of elements n from N below each m from M up to the first n above m
A school's task:
There are two sequences n_tab and m_tab.
For every element m in m_tab ...
- 171
2
votes
1
answer
256
views
Pre-calculate attacks in a chess game
I'm writing (or at least trying to write) a chess engine in C++. This is the first time I write code in C++, and I use this project to practice. Anyway, I'm following the general guidelines of a ...
- 105
2
votes
1
answer
3k
views
Assignment function for Intervals container
I found the two related questions but they, however, do not answer my question:
interval map implementation
Where exactly does my code not adhere to the specification of the key and value type?
The ...
- 121
6
votes
1
answer
516
views
Doubly linked list first fit free list malloc/free in Python
As an exercise I've implemented malloc and free in Python as a first fit free list as described here. This tracks which blocks are free in a doubly linked list that is sorted by the address of the ...
- 163
2
votes
1
answer
86
views
Merge Sort with Minimum Sufficient Variables, Verbosity and better Space Complexity
The majority of merge sort implementations searched online are provided with unnecessary variables and code lines. Here is an attempt to reduce that. However, does passing back the subArray as return ...
- 459
0
votes
2
answers
304
views
Binary Search written in python with O(n) [closed]
def search(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
if nums[i] == None:
return -1
I think ...
- 53
-2
votes
1
answer
419
views
Number Plate Generation Program
I wrote a number plate generation program. The program generates number plates for a car registered with a specific Memory Tag and on a specific date.
Number plates use the following format: (2 letter ...
- 21
3
votes
2
answers
467
views
Add two numbers represented as digit strings
This algorithm adds two numbers digit by digit using their string representations.
I am wondering what the time and space complexities of the following algorithm are. In particular, I am wondering ...
- 501
1
vote
2
answers
1k
views
Leetcode 55. Jump Game solution
I was working on Jump Game problem on leetcode
Question
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your ...
- 189
1
vote
1
answer
414
views
Printing subarrays ⚡
I was trying to to print all subarrays of an array in quadratic time. Here is my code:
...
1
vote
1
answer
120
views
Calculate maximum value of expression for potential associations
I have an algorithm that calculates the maximum value of an expression that is made from numbers and * or + by adding parentheses.
It has 3 nested loops, so the time complexity should be N^3
...
- 11
1
vote
2
answers
494
views
0
votes
1
answer
137
views
Time complexity of several methods of reversing a domain name string
Note: I'm aware of this existing post which is similar. However, it does not address all my questions sufficiently.
I have the following three functions, all of which do the same thing: reverse a ...
- 267
3
votes
1
answer
580
views
Finding the minimum element of a stack of numbers
As part of an online programming challenge, I wrote a program that implements a stack of integers, supporting adding and removing elements, finding the last inserted element, and the minimum element. ...
- 131
1
vote
2
answers
441
views
group countries by language in JavaScript
I need a better implementation than the below code (O(N) Solution), I am grouping countries by language ( data ) is the countries JSON, each country could have 0, 1 .. or more language as the object ...
- 19
0
votes
2
answers
1k
views
Separating odd numbers and even numbers into two vectors in C++
I'm learning C++, and would like some guidance. I'm pretty sure I'm doing something wrong.
This algorithm runs in O(n) time and uses O(n) external space. Could I make a more efficient algorithm for ...
- 13
4
votes
1
answer
221
views
Brute force to solve refund amount in a payment/invoice domain
I work at a major Swedish insurance company. I'm in charge of a service that matches bank payments with invoices. I will not show the details of that match logic. But one outcome of the match is that ...
- 690
-2
votes
2
answers
156
views
2
votes
2
answers
319
views
Find the highest product of three numbers in a list (Python)
I wrote the below as a solution to:
Problem
Find the highest product of three numbers in a list
Constraints
Is the input a list of integers?
Yes
Can we get negative inputs?
Yes
Can there be ...
- 197
1
vote
2
answers
344
views
SumList Cracking the coding Interview
Sum of 2 numbers, represented with linked lists, where digits are in backward order or forward order.
Backward order Example
INPUT:(7->1->6) + (5->9->2) = 617+295
OUTPUT: 2->1->9 = ...
- 13
0
votes
2
answers
340
views
Optimizing methods with multiple if checks on getter values
I have a method where I fetch user input, check if certain values exist, and based on that build my own custom input object that I would use to search in a database. The code for the search method is ...
- 121
3
votes
1
answer
279
views
Find the largest decrease in a sequence of numbers
I have written a function that takes as input a list of 5 numbers, then the program's goal is to return the largest drop in the list. It is important to understand that [5, 3, ...] is a decrease of 2 ...
1
vote
3
answers
247
views
Finding unique top sums from multiple lists
My question arises from this post on MSE where I have provided an answer to solve the question :
There are multiple lists given. The number of lists is arbitrary.
Each list contains numbers and is ...
- 121
1
vote
2
answers
1k
views
URLify a given String - replace spaces with %20
I have written a code to replace all spaces in a String with %20.
...
- 113
2
votes
2
answers
481
views
Can I further optimize this solution for HackerRank's “Making Candies”?
My C++ solution for HackerRank's "Making Candies" problem, reproduced below, is as optimized as I can make it and appears similar to what others say are optimal solutions. However, six of ...
- 298
3
votes
1
answer
148
views
Substring search in Java
I am trying to make an algorithm that will find the index of a given substring (which I have labeled pattern) in a given String (...
- 361
2
votes
2
answers
195
views
Optimize nested loops for counting the total number of selections
The question is: To select 2 numbers out of n positive integer inputs (order matters), where the number that is placed anywhere before the second must be greater than the second by a given number m. ...
2
votes
0
answers
130
views
Monotonic stack - complexity analysis
I tried following the official solution of LC975 (https://leetcode.com/problems/odd-even-jump/), using a monotonic stack - i.e., I reimplemented their solution (Approach 1) from python in C++.
TLDR ...
- 322
3
votes
4
answers
229
views
Is this an efficient/correct way to get largest Prime factor?
Is this an efficient way to get the largest prime factor of a given number? Other solutions I found involved nested algorithms.
...
- 143