Skip to main content

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.

Filter by
Sorted by
Tagged with
2 votes
2 answers
57 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 ...
5 votes
1 answer
369 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 ...
2 votes
1 answer
181 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 ...
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 ...
7 votes
1 answer
251 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 ...
5 votes
2 answers
555 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 ...
3 votes
1 answer
69 views

Proving a conjecture given a set of clauses - calculating complexity

I have written this Perl program to prove a conjecture given a set of clauses. I've actually posted some code from it on here in another question. This time it's all done, and I've made it as fast as ...
4 votes
1 answer
132 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 ...
6 votes
4 answers
567 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....
1 vote
1 answer
94 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 ...
4 votes
3 answers
584 views

Leetcode 3sum problem solution

The problem is: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where ...
2 votes
4 answers
2k views

Reverse the digits of an Integer

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Return 0 if the result overflows and does not fit in a 32 bit signed integer This is my approach: <...
4 votes
1 answer
494 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 ...
3 votes
1 answer
127 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 ...
-2 votes
2 answers
79 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. ...
3 votes
2 answers
544 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 <...
4 votes
2 answers
2k views

Time and Space Complexity of Prime factorization

I have written a function that prints all the prime factors for a given number. Here is my code ...
3 votes
4 answers
193 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. ...
3 votes
2 answers
256 views

Time and space complexity of base conversion code

I have an algorithm that performs the base conversion. The input is a string and two ints b1 and b2. The string represents an ...
4 votes
6 answers
3k views

Award Budget Cuts implementation in Java

PRAMP Award Budget Cuts The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they’re facing. Originally, the committee ...
3 votes
2 answers
114 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
106 views

Binary search of 2D matrix

I have written code as below: ...
1 vote
1 answer
340 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 ...
2 votes
2 answers
95 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 ...
4 votes
2 answers
3k views

Finding whether there exists a pair of numbers in a set having a given product

Devise an algorithm that will operate on a number x and a set of n distinct numbers such that in \$O(n \lg n)\$ time, the algorithm indicates whether or not there are two numbers in the set that have ...
1 vote
0 answers
23 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 ...
2 votes
1 answer
207 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 ...
4 votes
2 answers
160 views

Modelling Immerman–Szelepcsényi in Haskell

I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here. ...
2 votes
1 answer
58 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 ...
1 vote
2 answers
413 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 ...
0 votes
1 answer
367 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 ...
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 ...
-2 votes
1 answer
392 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 ...
6 votes
1 answer
459 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 ...
0 votes
0 answers
204 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. ...
0 votes
2 answers
279 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 ...
1 vote
0 answers
75 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 ...
3 votes
2 answers
421 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 ...
0 votes
2 answers
2k views

Subset sum simple iterative implementation

Here is the simplest iterative implementation of Subset sum problem that I could come up with1, as a follow up to this recursive implementation of the same problem: ...
2 votes
0 answers
114 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 ...
1 vote
4 answers
335 views

Given the arrival times of people at a door, resolve their passage times

I was trying to solve the following question: You are given 2 arrays: one representing the time people arrive at a door and other representing the direction they want to go (in or out) You have to ...
1 vote
1 answer
353 views

Printing subarrays ⚡

I was trying to to print all subarrays of an array in quadratic time. Here is my code: ...
4 votes
1 answer
2k views

Swift - Finding longest binary gap of a given integer

I recently had the chance to try Codility's algorithm training, and the very first one in the list is finding the longest binary gap of a given integer. I tried to implement this in Swift, and after ...
2 votes
4 answers
276 views

Long arithmetic addition in JS

The implementation of the algorithm which adds two number in string form with arithmetic rules. ...
0 votes
2 answers
415 views

Algorithm for twoSum

This is my PHP algorithm for the twoSum problem in leetCode: ...
0 votes
1 answer
95 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 ...
9 votes
3 answers
4k views

Find the smallest positive integer that is absent from a given array

I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find ...
2 votes
1 answer
1k views

Median of two sorted arrays

The task is to find the median of two Arrays. I have an O(n) solution. Can it be written in a better time complexity? ...
2 votes
1 answer
1k views

Median of two sorted arrays JavaScript

Trying to find the median of two sorted arrays in O(log(m+n)) or better. I believe this is O(log(m+n) or O(log(m)) or O(n). ...
3 votes
1 answer
537 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. ...

1
2 3 4 5
9