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.
413
questions
3
votes
2
answers
513
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 <...
- 212
1
vote
1
answer
86
views
3
votes
2
answers
98
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
117
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
93
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 ...
- 127
1
vote
0
answers
22
views
Designing a font definition with multiple variants per glyph
My project penhand tries to visualize the process of writing with a pen. Part of the project is an engine that converts text entry into a sequence of glyphs that are then rendered as animation into a ...
- 151
2
votes
1
answer
161
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
1k
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
319
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
57
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
0
answers
145
views
Program to generate a tree of permutations
There is a computation I'm doing with permutations (permutations of varying length of an entire interval [1,N] for some N) in python that I feel could be faster.
...
- 225
0
votes
2
answers
278
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 ...
- 45
-2
votes
1
answer
250
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
1
vote
0
answers
70
views
Traveling salesman (Dynamic Approach) retrieve path without losing on time complexity
It is difficult to find resources on above programming problem therefore I've decided to ask a question on this forum. Using memoization and dynamic programming we can obtain a code that gives \$O(2^N ...
- 11
3
votes
2
answers
314
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
1
answer
498
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
282
views
Printing subarrays ⚡
I was trying to to print all subarrays of an array in quadratic time. Here is my code:
...
0
votes
0
answers
61
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
...
- 1
0
votes
2
answers
383
views
0
votes
1
answer
91
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 ...
- 295
3
votes
1
answer
454
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
381
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
880
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
156
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 ...
- 670
-2
votes
2
answers
103
views
2
votes
2
answers
259
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 ...
- 187
1
vote
2
answers
282
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
259
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
230
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 ...
0
votes
3
answers
208
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 ...
- 101
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
383
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 ...
- 258
3
votes
1
answer
113
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 (...
- 351
2
votes
2
answers
142
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
110
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
182
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.
...
- 133
4
votes
1
answer
418
views
strstr implementation with python and sets
Please review my strstr implementation in terms of time/space efficiency and overall readability. I am preparing for a coding assessment coming up as I am looking to pivot my career from Physics to ...
- 41
1
vote
0
answers
82
views
Sorting Algorithm using Modified Merge sort
I've been messing around with merge sort. Instead of doing a recursive division of the array I chose to keep keep track of the middle index of every three numbers. Using the index of the middle number,...
- 43
4
votes
2
answers
4k
views
Merge arrays in objects in array based on property
I have the following code which takes an array that might have duplicate ids and will merge the items of those duplicate, and ...
- 189
4
votes
1
answer
640
views
Performant Sort function for big arrays
In sort(arr), I want to sort an array. Children must be beneath their parent. And children of the same parent are sorted using ...
- 143
2
votes
2
answers
786
views
LeetCode 3Sum Java Solution
I have this Java solution to LeetCode's 3Sum problem.
I would be really grateful if I could get feedback on correctness, scalability, efficiency, coding best practices, and OOP design.
I'm relatively ...
- 31
2
votes
0
answers
180
views
2D Array Word Search: Complexity and Optimization
🧩 Objective
Determine whether a given word is contained in a 2D Array word search.
🔎 Question
1. What are the time and space complexities of the current algorithm?
Time complexity
Linear: \$O(2(r * ...
- 239
0
votes
1
answer
326
views
Generate unique string permutations recursively
🧩 Objective
Write a recursive method for generating all permutations of an input string. Return them as a set.
See: Recursive String Permutations - Interview Cake
🔎 Questions
1: How does the ...
- 239
1
vote
1
answer
549
views
Most efficient solution for USACO: Cow Gymnastics - Python
I was trying to figure out this problem, and I did. However, my code is so abhorrently ugly that I want to tear out my eyeballs when I look at it:
...
3
votes
2
answers
125
views
Cyclomatic Complexity (complexity)
I have a program for finding shortest distance/path and I got a correct answer but I am getting an issue i.e., "Function 'shortestPath' has a complexity of 9. Maximum allowed is 6." This is ...
- 31
3
votes
1
answer
398
views
Ensuring if an object is Assignable from a class type
I am trying to ensure type in the below method. How to reduce its cognitive complexity to below 15 from the current 27? It looks more readable as it is? Is there a way to break this down to make it ...
- 33
5
votes
1
answer
605
views
01 Matrix is too slow when solved using DFS
I tried solving Leetcode 01 Matrix problem.
It is running too slow when solved using DFS approach.
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance ...
- 129
3
votes
2
answers
834
views
Most Efficient Solution for USACO: Triangles - Python
I'm trying to solve this problem with Python 3.8. In my code, I used 3 nested for loops to check every single point and storing the largest area with each set of points. This program works fine, but ...
7
votes
2
answers
741
views
Best Algorithm for solving USACO: Photoshoot - Python
I was trying to solve this problem with Python 3.8. I couldn't find a way other than to brute-force calculate all the possible permutations then check which permutation was valid. The program works ...
-4
votes
1
answer
62
views
What is the time complexity problem I need to manage on a Hackerank "Ransom Note" - my code runs perfectly [closed]
I am trying to solve the "Ransom Note" problem on hackerank.
Why isn't my code getting submitted?
What can I do differently?
is my total time complexity, in this case, it is O(n^2)?
...
- 159